LeetCode 630. 课程表 III

2024-01-08 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 630. 课程表 III

题意分析

要什么：每门课给出耗时 duration 和关门时间 lastDay，从第 1 天开始一门接一门地上，中间不能并行、不能中断，要求每门课的结束时刻不超过它自己的 lastDay，问最多能修完几门。
约束透露的信号：题目只问「最多几门」，不问是哪几门、也不问顺序，说明答案对「选中集合的内部排列」不敏感——这就允许我们把已选课程当成一个可以随时反悔、随时替换的池子，而不必回溯具体方案。课程数量到 $10^4$ 级别，$O(n^2)$ 的逐个尝试会吃力，$O(n \log n)$ 是目标量级。
边界：单门课自身 duration > lastDay 时永远无法被选中；总耗时正好等于 lastDay 是合法的（闭区间）；所有课都选不上时答案为 0；课程之间没有先后依赖，这点和「课程表 I / II」完全不同，别被标题带偏去建图。

解法：排序 + 最大堆（贪心）

核心思路

先想暴力：这是一个选子集的问题，$2^n$ 枚举显然不可行；改成「按某个顺序逐门决定选或不选」的搜索，最坏仍是指数级。
突破口在于一个可以证明的重排引理：如果一组课程能被全部修完，那么把它们按 lastDay 升序上，同样能全部修完。因为交换两门相邻且 lastDay 逆序的课，只会让先上的那门更早结束、后上的那门结束时刻不变，不会破坏任何一门的截止约束。既然存在最优解一定长成「按 lastDay 升序」的样子，我们就可以把整体排序，问题变成「按固定顺序逐门决策」。
接着是反悔贪心：先无脑把当前课加进来，一旦总时长超了截止时间，就丢掉已选课程里耗时最长的那一门。为什么丢最长的最优？因为丢任意一门都能让已选数量减 1，代价相同；而丢耗时最长的能把总时长压得最低，给后面所有课留出最多空间。注意被丢掉的那门可能就是刚加进来的，这时相当于「当前课不选」，两种情况被统一成同一段代码。
由此写出要维护的不变量：遍历到第 i 门课（已按 lastDay 升序）时，堆中保存的是「只考虑前 i 门课、能同时修完的课程数最多、且在数量最多的前提下总耗时最小」的那个方案的各门课时长，time 等于堆内元素之和。「数量最大 + 同数量下耗时最小」这两条一起构成不变量，缺一不可：只有耗时也最小，才能保证这个方案对后续课程是最不设限的，从而贪心不会因为局部选择堵死未来。

解题步骤

把 courses 按 lastDay 升序排序。为什么：重排引理保证存在按截止时间升序完成的最优解，排序后我们才能用「前缀 + 反悔」的线性框架代替子集枚举；如果不排序，后面出现的一门早截止课程可能让之前所有决策全部作废。

准备一个最大堆和累计变量 time = 0。为什么用最大堆：反悔时要找的是「已选课程里耗时最长的一门」，这是一次动态的取最大值 + 删除操作，堆恰好是 $O(\log n)$ 完成它的结构；用数组线性扫会退化成 $O(n^2)$。

遍历每门课 (d, end)，先执行 time += d 并把 d 入堆。为什么先加再判断：贪心的核心是「总是先尝试」，只有加进来才知道会不会超时；而且加进来后如果要反悔，被弹出的可能正是它自己，逻辑天然自洽，不需要写「当前课能否放下」的分支。

若 time > end，弹出堆顶最大值 dMax 并执行 time -= dMax。为什么只弹一次就够：进入这一轮之前不变量成立，即 time 不超过上一门课的截止时间，加入 d 后最多超出 d，而堆顶的最大值至少是 d，所以弹一个必然让 time 重新合法。也正因为如此，堆的大小最多减 1，「已选数量」在整轮遍历中不会倒退超过一门。

遍历结束后返回堆的大小。为什么不是 time 或计数器：堆里剩下的元素个数就是最终方案的课程数，反悔操作已经把它维护得始终正确，另设计数器反而容易和弹出逻辑对不上。

以 courses = [[100,200],[200,1300],[1000,1250],[2000,3200]] 走一遍。排序后顺序变成 [100,200]、[1000,1250]、[200,1300]、[2000,3200]。第一门：time = 100，堆 {100}，100 ≤ 200 不反悔。第二门：time = 1100，堆 {1000, 100}，1100 ≤ 1250 不反悔。第三门：time = 1300，堆 {1000, 200, 100}，1300 ≤ 1300 恰好取等，闭区间合法所以不反悔——这里如果把判断写成 >= 就会误弹掉 1000，答案掉到 2。第四门：time = 3300，堆 {2000, 1000, 200, 100}，3300 > 3200 触发反悔，弹出最大的 2000，time 回到 1300，堆剩 {1000, 200, 100}。返回堆大小 3，对应修完前三门、总耗时 1300 天。

代码实现

// 核心实现：排序 + 最大堆（贪心），维护必要状态并避免重复处理。
class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int time = 0;

        for (int[] c : courses) {
            int d = c[0];
            int end = c[1];
            time += d;
            pq.offer(d);

            if (time > end) {
                time -= pq.poll();
            }
        }

        return pq.size();
    }
}

// 核心实现：排序 + 最大堆（贪心），维护必要状态并避免重复处理。
func scheduleCourse(courses [][]int) int {
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })

    h := &maxHeap630{}
    heap.Init(h)

    time := 0
    for _, c := range courses {
        d, end := c[0], c[1]
        time += d
        heap.Push(h, d)
        if time > end {
            time -= heap.Pop(h).(int)
        }
    }

    return h.Len()
}

type maxHeap630 []int

func (h maxHeap630) Len() int { return len(h) }
func (h maxHeap630) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap630) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *maxHeap630) Push(x any) { *h = append(*h, x.(int)) }
func (h *maxHeap630) Pop() any {
    old := *h
    v := old[len(old)-1]
    *h = old[:len(old)-1]
    return v
}

复杂度分析

时间复杂度：$O(n \log n)$。凭什么：排序一次 $O(n \log n)$；主循环每门课最多一次入堆、一次出堆，单次堆操作 $O(\log n)$，合计 $O(n \log n)$，两部分同阶。

空间复杂度：$O(n)$。凭什么：堆最坏装下全部 $n$ 门课的时长；排序在 Java 上对对象数组使用归并排序另需 $O(n)$ 辅助空间，Go 的 sort.Slice 为原地快排 $O(\log n)$ 栈空间，总量仍是 $O(n)$。

关键点总结

反悔贪心的模板：先无条件接受当前元素，破坏约束时再撤销「代价最大」的历史决策。它比「先判断能不能放」的朴素贪心强，因为它允许用后来的小元素替换掉早先的大元素。

贪心题的正确性通常靠两块拼图：一是交换论证给出最优解的规范形态（这里是按截止时间升序），二是不变量说明每一步维护的东西确实是当前前缀的最优（这里是「数量最大且同数量下耗时最小」）。面试里这两块讲清楚，代码只是附属品。

认准「动态取极值 + 删除」就该想到堆。是最大堆还是最小堆，取决于你要撤销的是最贵的还是保留最贵的——本题撤销最贵，故用最大堆；而「IPO」那类要挑最赚的，用的是最大堆但方向相反，别机械套用。

面试视角：这题最容易被追问「为什么弹出最长的那门就一定最优」和「为什么每次只弹一次」。答案分别是「同样减少一门课的前提下释放的时间最多」和「加入前时间合法、新增量不超过堆中最大值」，两句话都要能张口就来。

标题里的「课程表」是干扰项。没有先修关系就没有图、没有拓扑排序，读题时要以约束为准而不是以题名为准。

易错点总结

错误写法：按 duration 升序排序而不是按 lastDay；用例 [[2,2],[3,10],[1,10]] → 排成 [1,10]、[2,2]、[3,10]，处理到 [2,2] 时已耗掉 1 天，time 变 3 超过截止 2，被迫弹掉一门，最终返回 2；按 lastDay 升序则依次修 [2,2]、[3,10]、[1,10]，总耗时 6 天全部合法，正确答案是 3。

错误写法：把超时判断写成 time >= end；用例 [[100,200],[1000,1250],[200,1300]] → 第三门结束时 time = 1300 恰等于 end，被误判为超时弹掉 1000，返回 2，正确答案是 3。

错误写法：只在 time + d <= end 时才把课入堆，超时就直接跳过；用例 [[5,5],[4,6],[2,6]] → 先修耗时 5 的课占满到第 5 天，之后 5 + 4 和 5 + 2 都超过截止 6，两门全被跳过，返回 1；带反悔的版本会在第二门时用 4 换掉 5、第三门时把 2 也装进去，返回 2。丢掉反悔就丢掉了「用小课替换大课」的能力。

错误写法：用最小堆；用例 [[1,2],[5,10],[2,10]] → 第三门超时后弹出的是耗时 1 的课，time 只降 1 仍然超时，或者留下大课堵死后续，最终课程数偏少。

错误写法：超时后用 while (time > end) 反复弹出；用例正常数据 → 结果虽不会错，但掩盖了「每轮最多弹一次」这个关键性质，面试被追问时说不清；更糟的是若循环里忘记堆空判断，堆被弹空后再弹会抛异常。

错误写法：返回一个自增的计数器而不是堆大小，且反悔时忘记减一；用例 [[100,200],[200,300],[1000,1250]] → 计数器数到 3，实际堆里只剩 2 门，返回值偏大。

错误写法：弹出堆顶时忘记同步 time -= dMax；用例 [[2000,3200],[100,200]] 排序后为 [[100,200],[2000,3200]] 且再追加一门 → time 一直虚高，后续所有课都被误判超时，答案严重偏小。

错误写法：Java 里用 PriorityQueue<int[]> 存 (duration, lastDay) 却按 lastDay 建堆；用例任意多门课 → 反悔时弹出的是截止最晚的课而不是最耗时的课，time 下降幅度不可控，答案偏小。

错误写法：Go 里实现堆时 Less 写成 h[i] < h[j]；用例 [[1,10],[9,10],[2,10]] → 变成最小堆，超时后弹出 1 而不是 9，返回结果偏小。

相似题目

题目	难度	考察点
502. IPO	困难	同样是排序 + 堆，但堆用来「解锁并挑最优」，不涉及撤销已做决策
253. 会议室 II	中等	堆里存的是结束时间而非耗时，求的是并发峰值而不是最大可选数量
621. 任务调度器	中等	贪心对象从「截止时间」换成「剩余次数」，靠数学公式即可绕开堆