LeetCode 课程表 III

@author：Jingdai
@date：2021.09.17

题目描述

这里有 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 天完成它，这已经超出了关闭日期。

思路及代码

首先看两个课程的情况，如果有 <t1, d1> 和 <t2, d2> 两门课，d1 <= d2，应该先选修哪一门课呢？假设现在的时间是 x，如果先选第1门课，则需要满足：

x + t1 <= d1
x + t1 + t2 <= d2

如果先选第2门课，则需要满足：

x + t2 <= d2
x + t1 + t2 <= d1

同时如果先选第2门课，则根据 x + t1 + t2 <= d1，可以推出x + t1 <= d1;同时根据 x + t1 + t2 <= d1 且 d1 <= d2 可以推出 x + t1 + t2 <= d2，所以如果可以先选第2门课，则一定可以先选第1门课，反之则不能推出，可以举个例子如<1, 2> 和 <10, 12> 。所以，优先选择截止时间早的肯定是最优的方案。根据此，我们可以先按 d 从小到大将课程进行排序，然后依次进行选择。

在选择的过程中，假设到第 n + 1 门课<tn+1, dn+1>了，是否应该选择呢？

前 n 门课中，假设选了k门，且总耗时最短，那么有：

t1 + t2 + ... + tk <= dn

如果：

t1 + t2 + ... + tk + tn+1 <= dn+1

那么说明这门课可以选，直接选择，开始看下一门课。否则，说明这门课不能直接选，前 n+1门课仍然只能选择 k门，但是如果tn + 1比前面的某一门课耗时短，那么第n+1门课不就可以替换掉前面的某一门课，且使得耗时更加短嘛，这样使得后面的选择过程中更容易满足条件。那应该替换哪一门课呢？显然应该替换耗时最长的那一门课，虽然选择课程的数量不变，但是总耗时减少了。证明如下：

t1 + t2 + ... + tj + ... + tk <= dn   // 选n+1门课前（假设tj最大且tj > tn+1）
由于排序，则
t1 + t2 + ... + tj + ... + tk <= dn+1
由于 tj > tn+1，放缩
t1 + t2 + ... + tn+1 + ... + tk <= dn+1
即满足条件，且总耗时最小

由于我们每次都需要保存之前的耗时最长的课程，所以我们使用一个堆来保存这样的记录，这样就不用每次去遍历选择的课程。

总结一下就是，先将全部课程按截止时间升序排列，然后依次选取。如果到第 k 门课程可以选取，则直接选择。如果不能选择，假设之前已经选择了 m 门课，说明现在也只能选择 m 门课，既然只能选择 m 门课，我们要选择耗时最短的 m 门课，即将耗时最多的那门课删除，为后面的选课多争取一些时间。

最后的代码如下。

public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses, (c1, c2) -> c1[1] - c2[1]);
    PriorityQueue<int[]> heap = new PriorityQueue<>((c1, c2) ->c2[0] - c1[0]);
    int now = 0;
    for (int[] course : courses) {
        if (course[0] > course[1]) {
            continue;
        }
        if (now + course[0] <= course[1]) {
            heap.offer(course);
            now += course[0];
        } else {
            if (heap.peek()[0] > course[0]) {
                now -= heap.peek()[0];
                heap.poll();
                heap.offer(course);
                now += course[0];
            }
        }
    }
    return heap.size();
}