题目大意：
课程表 III
这里有 n 门不同的在线课程，他们按从 1 到 n 编号。每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。
给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。
示例：
输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出: 3 解释: 这里一共有 4 门课程, 但是你最多可以修 3 门: 首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。 第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。 第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。 第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。
提示:
- 整数 1 <= d, t, n <= 10,000 。
- 你不能同时修两门课程。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=650
解题思路分析：
这道题需要使用到排序和优先队列PriorityQueue。另外解题的核心思路也会利用到贪心思想。
- 首先我们需要明确一点，先学习deadline靠前的可以省下更多的时间去学习其他课程。虽然这不一定是全局最优解，但我们有其他办法在后面进行修正。
- 根据第一点的结论，我们将课程数组按照deadline进行升序排序。
- 创建一个优先队列PriorityQueue，用来保存可以学习的课程，Queue中保存所有已选课程所消耗的时间，并且时间按照由多到少降序排列。另外建立一个变量day，代表当前日期。
- 循环课程列表从中取出每一门课，如果当前日期day加上该课消耗的时间小于等于这门课程的deadline，那么我们将这门课程所消耗的时间加入到Queue中。
- 如果当前日期day加上当前课程消耗的时间大于这门课的deadline，说明从当前日期开始到deadline之前无法完成该课程的学习。那么我们可以考虑从Queue中拿掉一门最消耗时间的课程（一定要大于当前课程的时间，否则没有意义），来换取更多的时间学习当前这门课。然后再将当前课程加入到Queue中。这样一来虽然一减一加，Queue中元素的个数没有发生改变，但是我们去掉了时间最长的课程，也就是将Queue中的总时间减少，对于全局结果来说会做出一定的优化。重复上述过程直到循环完每一节课。
- 最终Queue中元素的个数即是返回结果
实现代码：
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses,(a,b)->a[1]-b[1]); // 按照deadline进行升序排序
// 保存所有可选课程
PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->b-a);
int day=0; // 当前日期
// 循环所有课程
for(int[] c : courses){
// 如果从当前开始学这门课，能赶上该课的deadline的话
if(day+c[0]<=c[1]){
q.offer(c[0]); // 将该课程的时长加入Queue
day+=c[0]; // 同时更新日期为这门课学完后的日期
}else{ // 如果从当前开始学这门课，不能赶上该课的deadline的话
// 如果已选课程中时长最大的课程大于当前课程的时长
if(q.size()>0&&c[0]<q.peek()){
// 放弃学习时长最长的那门课
int remove=q.poll();
// 日期减去那门课要花费的时间
day-=remove;
// 将当前课程加入Queue
q.offer(c[0]);
// 同时更新日期为当前这门课学完后的日期
day+=c[0];
}
}
}
return q.size();
}本题解法执行时间为30ms。
Runtime: 30 ms, faster than 83.72% of Java online submissions for Course Schedule III.
Memory Usage: 48.4 MB, less than 100.00% of Java online submissions for Course Schedule III.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-630-course-schedule-iii-解题思路分析/