LeetCode - 630 课程表Ⅲ
目录
题目来源
题目描述
示例
提示
题目解析
算法源码
题目来源
630. 课程表 III - 力扣（LeetCode）
题目描述
这里有 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 <= 104
- 1 <= durationi, lastDayi <= 104
题目解析
本题虽然是一道hard题目，但是有固定的解题套路，因此一旦掌握解题套路，本题就很easy了。
本题的解题套路如下：
首先，将courses数组元素按照结束时间lastDayi进行升序排序。
然后，定义一个优先队列，course的durationi越大，优先级越高。
之后，定义一个curDay来记录当前时间，初始为0，
接下来，遍历courses数组，这样遍历出来的每一个course都是最接近curDay的，设courses[i] = [durationi, lastDayi]，如果：
- curDay + durationi <= lastDayi，则说明当前时间如果选择上courses[i]，则可以在其结束时间前学完。此时我们可以将courses[i]加入优先队列中，并更新curDay = curDay + duration。
- curDay + durationi > lastDayi，则说明当前时间如果选择上courses[i]，则无法在其结束时间前学完，此时我们应该做如下判断：
题目要求我们上最多的课，因此我们应该尽量上duration短的课程。
此时，我们应该获取优先队列堆顶元素，因为优先队列是按照duration设置优先级的，duration越大优先级越高，越靠近堆顶。
如果当前课程的durationi < 优先队列最大的top_duration，则有必要将优先队列堆顶的课程弹出，即不学习这门课程了，这样就节省出了top_duration的时间，并且curDay也会跟着降低，即curDay = curDay - top_duration。
此时，curDay + durationi <= lastDayi 必然成立，因此我们可以学习courses[i]课程，此时我们应该将courses[i]加入优先队列，并更新curDay = curDay + durationi。
算法源码
class Solution {public int scheduleCourse(int[][] courses) {Arrays.sort(courses, (a, b) -> a[1] - b[1]);PriorityQueue pq = new PriorityQueue<>((a,b) -> b - a);int curDay = 0;for(int[] course : courses) {int duration = course[0];int lastDay = course[1];if(curDay + duration <= lastDay) {pq.offer(duration);curDay += duration;} else {if(pq.size() == 0) {continue;}int maxDuration = pq.peek();if(duration < maxDuration) {pq.poll();pq.offer(duration);curDay += duration - maxDuration;}}}return pq.size();}
} 