630_课程表III

难度：困难

题目

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

你的学期从第 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 天完成它，这已经超出了关闭日期。

示例二：

输入：courses = [[1,2]]
输出：1

示例三：

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

提示

  • $1 <= courses.length <= 10^4$
  • $1 <= duration_i, lastDay_i <= 10^4$

解题

整体思路就是： 优先修读dll近的 放弃的时候则放弃修读时间长的 给之后的课程留更多的时间

可以用优先队列模拟这个过程；堆顶放修读时间最长的课程；按照ddl升序排列依次修读。
如果可以修读，更新总修读时间。
如果不可修读，看花费最长时间的课程是哪门，我们把它替换掉即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int scheduleCourse(int[][] courses){
  // 按照截止时间排序，然后按照持续时间排序
  // 优先截止时间早，持续时间短的
  Arrays.sort(courses,(arr1, arr2)->arr1[1]==arr2[1]?arr1[0]-arr2[0]:arr1[1]-arr2[1]);
  // 优先队列
  PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a);
  int sum = 0;
  for (int[] course:courses) {
    int time = course[0], end = course[1];
    sum+=time;
    q.add(time);
    if (sum>end) sum-=q.poll();
  }
  return q.size();
}