课程表 III【LC630】](https://leetcode.cn/problems/course-schedule-iii/)
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
interesting
动态规划
- 思路
实现
class Solution { public int scheduleCourse(int[][] courses) { Arrays.sort(courses, (o1, o2) -> o1[1] - o2[1]); int n = courses.length; int maxTime = courses[n - 1][1]; int[] dp = new int[maxTime + 1];// 截至日期为i时最多可以完成的课程数 for (int[] course : courses){ for (int j = course[1]; j >= course[0]; j--){ dp[j] = Math.max(dp[j - course[0]] + 1, dp[j]); } } int res = 0; for (int count : dp){ res = Math.max(res, count); } return res; } }
复杂度
时间复杂度：O(n \log n+n^2)
空间复杂度：O ( log n + n )
反悔贪心
- 思路
- 局部最优：结束时间较早的课程优先进行
- 反悔贪心：当某一时刻能够完成的课程数量相同时，优先完成时长较短的课程，以使后续能完成更多的课程
- 全局最优：相同时间上更多的课
- 实现
使用大顶堆存储每门课程的耗时，并记录当前所有课程的总耗时time
- 如果能完成当前课程，那么
time增加course[0]，将该课程放入堆中 - 如果不能完成当前课程，那么判断能否减少总耗时
- 如果能将堆顶元素移除，将该课程放入堆中
- 如果不能，不做任何操作
- 最后返回堆中元素个数
class Solution { public int scheduleCourse(int[][] courses) { Arrays.sort(courses, (a, b) -> a[1] - b[1]); // 按照 lastDay 从小到大排序 PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // 最大堆 int day = 0; // 已消耗时间 for (int[] c : courses) { int duration = c[0], lastDay = c[1]; if (day + duration <= lastDay) { // 没有超过 lastDay，直接学习 day += duration; pq.offer(duration); } else if (!pq.isEmpty() && duration < pq.peek()) { // 该课程的时间比之前的最长时间要短 // 反悔，撤销之前 duration 最长的课程，改为学习该课程 // 节省出来的时间，能在后面上完更多的课程 day -= pq.poll() - duration; pq.offer(duration); } } return pq.size(); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/course-schedule-iii/solutions/2436667/tan-xin-huan-neng-fan-hui-pythonjavacgoj-lcwp/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( n log n )
空间复杂度：O ( n )
