LC 630. Course Schedule III

https://leetcode.com/problems/course-schedule-iii/

同样这题有三个版本：

• 版本1 和 版本2 是拓扑排序问题，有O(V+E)的时间复杂度解法
• 版本3 稍微有点不同，其实是个贪心问题。这题看看 题解 有帮助。

题解写的非常好，说明了两个问题：

1. 为什么应该优先挑选deadline靠前的
2. 对于新的course，是应该直接加入，还是应该替换原有的安排

我们首先可以发现，如果两门课 (t1, d1) 和 (t2, d2) 满足 d1 <= d2，即后者的结束时间不晚于前者，那么我们先学习前者再学习后者总是最优的。因为如果先学习前者，即需要满足 x + t1 <= d1 且 x + t1 + t2 <= d2；如果先学习后者，则需要满足 x + t2 <= d2 且 x + t1 + t2 <= d1。如果后者中的 x + t1 + t2 <= d1 成立，那么显然有 x + t1 <= d1 且 x + t1 + t2 <= d1 <= d2，即前者一定成立；反之如果 x = 0, (t1, d1) = (2, 3), (t2, d2) = (5, 100)，那么前者成立且后者不成立。因此先学习前者再学习后者总是最优的。

基于上面的结论，我们可以将课程按照完成时间 d 递增排序。假设我们在前 i 门课中最多可以选取 k 门课，并且这 k 门课的总时长最短（称为最优方案），那么有下面的不等式：

• t1 + t2 <= d2
• t1 + t2 + t3 <= d3
• …
• t1 + t2 + … + tk <= dk

此时我们需要判断第 i + 1 门课 (t0, d0) 是否可选。如果选取的 k 门课的总时长 t 与 t0 之和小于等于 d0，即 t1 + t2 + … + tk + t0 <= d0 那么 (t0, d0) 一定可选，此时前 i + 1 门课的最优方案是选取 t1, t2, …, tk, t0 这 k + 1 门课。可以使用反证法来证明，假设可以选取超过 k + 1 门课，或者选取 k + 1 门课且总时长小于 t1 + t2 + … + tk + t0，那么我们去除 (t0, d0) 这门课，剩余的选取方案一定满足条件，且优于选取 t1, t2, …, tk 的方案，与之间的假设 t1, t2, …, tk 是最优方案相矛盾。

如果上述不等式不满足，那么我们找出 t1, t2, …, tk 中时间最长的那一门课 tj，如果 tj > t0，那么我们可以将 tj 用 t0 代替，即 t1, t2, …, tj-1, tj+1, …, tk, t0 是一种最优方案。这里同样可以使用反证法来证明。如果 tj <= t0，那么最优方案仍然为 t1, t2, …, tk。

因此我们依次遍历每一门课程，通过上面的方法，就可以得到最优方案。我们就可以通过优先队列在若干个数中选出最大值，在遍历每一门课程 (ti, di) 时，依次进行如下操作：

• 如果当前优先队列中所有课程的时间之和 t 与 ti 之和小于等于 di，那么就把 (ti, di) 加入优先队列中；
• 如果当前优先队列中所有课程的时间之和 t 与 ti 之和大于 di，那么找到当前优先队列中课程时间最大的课程 (tj, dj)（即为堆顶），如果 tj > ti，则将它移出优先队列，并把 (ti, di) 加入优先队列中。

在所有的课程都判断完毕后，优先队列中包含的课程数目就代表了最多能选择的课程数目。

Java现在的语法真是简洁啊 `PriorityQueue < Integer > queue = new PriorityQueue < > ((a, b) -> b - a);` 后面还是要重仓Java/JVM

class Item:
    def __init__(self, x, c):
        self.x = x
        self.c = c

    def __lt__(self, o):
        return self.x > o.x


class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        import heapq
        hp = []
        courses.sort(key=lambda x: x[1])

        acc = 0
        for c in courses:
            t, d = c
            if acc + t <= d:
                heapq.heappush(hp, Item(t, c))
                acc += t
                continue

            if hp and hp[0].x > t:
                acc += t - hp[0].x
                heapq.heapreplace(hp, Item(t, c))

        # print(sorted([x.c for x in hp], key = lambda x: x[1]))

        ans = len(hp)
        return ans