想要精通算法和SQL的成长之路 - 课程表III
- 前言
- 一. 课程表III（贪心+优先队列）
- 1.1 优先选择截止时间更小的课程
- 1.2 如果当前课程无法学习怎么办？
- 1.3 优化
前言
想要精通算法和SQL的成长之路 - 系列导航
一. 课程表III（贪心+优先队列）
原题链接
我们来分析一下题目：
- 我们同一时间只能学习一种课程。
- 题目中
courses是一个二维数组。每个小数组中，第一个数值代表：学习该课程的持续时间。第二个数值代表学习该课程的最晚时间。
1.1 优先选择截止时间更小的课程
那么我们应该如何优先选择要学习的课程？
- 优先选择截止时间早的课程。
例如有两个课程：[1,2] ,[3,6]。
- 如果先学前者：两个课程都可以学完，耗时总时间为
1+3 < 6。 - 如果先学后者：第二个课程耗时3天。已经超过第一个课程的截止日期。那么第一个课程就无法学习。
那么对于代码而言，我们需要对二维数组courses的第二个值做一个升序排序。然后我们从左往右选择课程去学习。
因此，我们首先应该对二维数组做一个排序：
Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
1.2 如果当前课程无法学习怎么办？
我们给个例子，有三个课程：[1,2] 、[3, 4]、[2, 5]。按照截止日期升序排序。
- 这时候，当选择到第三门课程的时候，发现
1 + 3 + 2 > 5，即第三个课程我们无法学习。那这时候咋办？ - 我们应该永远遵循一个规则：在学习相同个数课程的前提下，我们耗时应该越短越好。 为啥？前面的耗时短了，就有更多的时间给后面的课程学习了。
- 那么我们就应该和上一个课程作比较。
[3, 4]、[2, 5]中，我们应该优先选择耗时更短的课程，即[2,5]。
讲到这里，我们就意识到，在程序编码过程中：
- 我们需要记录我们已经选过的课程以及目前学习的总耗时。
- 同时我们还要对我们选过的课程的耗时做一个升序排序。即大根堆
// 大根堆，学习时长更长的在堆顶
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// 学习总耗时
int total = 0;
- 如果发现当前课程耗时比堆顶元素的耗时更短，那么择优选择当前课程。
for (int[] c : courses) {int duration = c[0];int lastDay = c[1];if (total + duration <= lastDay) {// 记录当前的学习总耗时还有课程total += duration;heap.offer(c);} else if (!heap.isEmpty() && heap.peek()[0] > duration) {// 若当前课程学习不了，那么拿当前堆顶元素（耗时最大）和当前课程的耗时作比较。若当前耗时更短。那么择优选择当前课程total = total - heap.poll()[0] + duration;heap.offer(c);}
}
最后返回堆的大小，即是选择的课程数量：
return heap.size();
完整代码如下：
public class Test630 {public int scheduleCourse(int[][] courses) {// 根据第二个值进行升序Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));// 大根堆，学习时长更长的在堆顶PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);// 学习总耗时int total = 0;for (int[] c : courses) {int duration = c[0];int lastDay = c[1];if (total + duration <= lastDay) {// 记录当前的学习总耗时还有课程total += duration;heap.offer(c);} else if (!heap.isEmpty() && heap.peek()[0] > duration) {// 若当前课程学习不了，那么拿当前堆顶元素（耗时最大）和当前课程的耗时作比较。若当前耗时更短。那么择优选择当前课程total = total - heap.poll()[0] + duration;heap.offer(c);}}return heap.size();}
}
1.3 优化
- 其实我们的大根堆并不需要存储一个数组，我们只关心它的耗时时长。
- 既然我们用大根堆（升序）去存储学习的课程了。我们可以不用自己去判断：当前课程的耗时 < 堆顶元素的耗时。我们直接无脑把当前课程丢给大根堆，让他自己做排序，然后无脑弹出堆顶元素（耗时最长）即可呀。因为弹出的元素也可能是当前课程。
- 说白了就是把比较的操作丢给了大根堆。
public class Test630 {public int scheduleCourse(int[][] courses) {// 根据第二个值进行升序Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));// 大根堆，学习时长更长的在堆顶PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);// 学习总耗时int total = 0;for (int[] c : courses) {int duration = c[0], lastDay = c[1];total += duration;heap.offer(duration);if (total > lastDay) {total -= heap.poll();}}return heap.size();}
}
