leetcode [630] 课程表 III
Contact me:
Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub
这里有 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 天完成它，这已经超出了关闭日期。
提示:
整数 1 <= d, t, n <= 10,000 。
你不能同时修两门课程。
我们首先可以发现，如果两门课 (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)加入优先队列中。
在所有的课程都判断完毕后，优先队列中包含的课程数目就代表了最多能选择的课程数目。
import heapq
class Solution:
def scheduleCourse(self, courses: List[List[int]]) -> int:
courses.sort(key=lambda x: x[1])
q = []
d = 0
for c in courses:
if d + c[0] <= c[1]:
d += c[0]
heapq.heappush(q,-c[0])
elif q and -q[0] > c[0]:
d += c[0] + heapq.heappop(q)
heapq.heappush(q,-c[0])
return len(q)