630. Course Schedule III

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

同样这题有三个版本:

题解写的非常好,说明了两个问题:

  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 门课的总时长最短(称为最优方案),那么有下面的不等式:

此时我们需要判断第 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) 时,依次进行如下操作:

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

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