想要精通算法和SQL的成长之路 - 课程表III

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 课程表III（贪心+优先队列）

原题链接

我们来分析一下题目：

1. 我们同一时间只能学习一种课程。
2. 题目中courses是一个二维数组。每个小数组中，第一个数值代表：学习该课程的持续时间。第二个数值代表学习该课程的最晚时间。

1.1 优先选择截止时间更小的课程

那么我们应该如何优先选择要学习的课程？

• 优先选择截止时间早的课程。

例如有两个课程：[1,2] ,[3,6]。

• 如果先学前者：两个课程都可以学完，耗时总时间为 1+3 < 6。
• 如果先学后者：第二个课程耗时3天。已经超过第一个课程的截止日期。那么第一个课程就无法学习。

那么对于代码而言，我们需要对二维数组courses的第二个值做一个升序排序。然后我们从左往右选择课程去学习。

因此，我们首先应该对二维数组做一个排序：

Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
1

1.2 如果当前课程无法学习怎么办？

我们给个例子，有三个课程：[1,2] 、[3, 4]、[2, 5]。按照截止日期升序排序。

1. 这时候，当选择到第三门课程的时候，发现 1 + 3 + 2 > 5 ，即第三个课程我们无法学习。那这时候咋办？
2. 我们应该永远遵循一个规则：在学习相同个数课程的前提下，我们耗时应该越短越好。 为啥？前面的耗时短了，就有更多的时间给后面的课程学习了。
3. 那么我们就应该和上一个课程作比较。 [3, 4]、[2, 5] 中，我们应该优先选择耗时更短的课程，即 [2,5]。

讲到这里，我们就意识到，在程序编码过程中：

1. 我们需要记录我们已经选过的课程以及目前学习的总耗时。
2. 同时我们还要对我们选过的课程的耗时做一个升序排序。即大根堆

// 大根堆，学习时长更长的在堆顶
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// 学习总耗时
int total = 0;
1
2
3
4

3. 如果发现当前课程耗时比堆顶元素的耗时更短，那么择优选择当前课程。

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

最后返回堆的大小，即是选择的课程数量：

return heap.size();
1

完整代码如下：

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.3 优化

1. 其实我们的大根堆并不需要存储一个数组，我们只关心它的耗时时长。
2. 既然我们用大根堆（升序）去存储学习的课程了。我们可以不用自己去判断：当前课程的耗时 < 堆顶元素的耗时。我们直接无脑把当前课程丢给大根堆，让他自己做排序，然后无脑弹出堆顶元素（耗时最长）即可呀。因为弹出的元素也可能是当前课程。
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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19