image

這里有 n 門不同的在線課程，按從 1 到 n 編號。給你一個數(shù)組 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 門課將會 持續(xù) 上 durationi 天課，并且必須在不晚于 lastDayi 的時候完成。

你的學(xué)期從第 1 天開始。且不能同時修讀兩門及兩門以上的課程。

返回你最多可以修讀的課程數(shù)目。

 

示例 1：

輸入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
輸出：3
解釋：
這里一共有 4 門課程，但是你最多可以修 3 門：
首先，修第 1 門課，耗費 100 天，在第 100 天完成，在第 101 天開始下門課。
第二，修第 3 門課，耗費 1000 天，在第 1100 天完成，在第 1101 天開始下門課程。
第三，修第 2 門課，耗時 200 天，在第 1300 天完成。
第 4 門課現(xiàn)在不能修，因為將會在第 3300 天完成它，這已經(jīng)超出了關(guān)閉日期。
示例 2：

輸入：courses = [[1,2]]
輸出：1
示例 3：

輸入：courses = [[3,2],[4,3]]
輸出：0
 

提示:

1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/course-schedule-iii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

題解

image

Swift

class Solution {
    func scheduleCourse(_ courses: [[Int]]) -> Int {
        let courseSorts = courses.sorted { $0.last! < $1.last! }

        // 總課程時間
        var total = 0

        var queue = [Int]()

        for cource in courseSorts {
            let ti = cource[0], di = cource[1]

            if total + ti <= di {
                total += ti
                queue.append(ti)
                queue.sort(by: <)

            } else if !queue.isEmpty, queue.last! > ti {
                total = total - queue.last! + ti

                queue.removeLast()

                queue.append(ti)

                queue.sort(by: <)
            }
        }

        return queue.count
    }
}

print(Solution().scheduleCourse([[7,17],[3,12],[10,20],[9,10],[5,20],[10,19],[4,18]]))
// print(Solution().scheduleCourse([[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]))

// print(Solution().scheduleCourse([[1, 2]]))
// print(Solution().scheduleCourse([[3, 2], [4, 3]]))
//
// print(Solution().scheduleCourse([[5, 5], [4, 6], [2, 6]]))

Dart

class Solution {
  int scheduleCourse(List<List<int>> courses) {
    courses.sort((List<int> a, List<int> b) {
      return a.last.compareTo(b.last);
    });

    print(courses);

    // 總課程時間
    var total = 0;

    var queue = <int>[];

    for (var cource in courses) {
      var ti = cource[0], di = cource[1];

      if (total + ti <= di) {
        total += ti;
        queue.add(ti);

        queue.sort();
      } else if (queue.isNotEmpty && queue.last > ti) {
        total = total - queue.last + ti;

        queue.removeLast();

        queue.add(ti);

        queue.sort();
      }
    }

    return queue.length;
  }
}

void main() {
  print(Solution().scheduleCourse([
    [7, 17],
    [3, 12],
    [10, 20],
    [9, 10],
    [5, 20],
    [10, 19],
    [4, 18]
  ]));
}