image

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

 

示例 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 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
示例 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

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]
  ]));
}