LeetCode 630. 课程表 III

约 5 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节
标签
数组 排序 贪心 堆（优先队列）

题目描述

✅ 630. 课程表 III

image-20260929102019662

image-20260929102019781

题意分析

每门课程有持续天数和最晚完成日，从第 1 天开始学习，课程不能同时进行。可以选择并安排课程顺序，目标是让按各自截止日期完成的课程数量最多，恰好在截止当天完成也合法。

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

核心思路

[!blue]
先按截止时间排序，再在超时时删除最长课程。 任意可行安排都能改成截止时间升序：若相邻两课的截止顺序相反，交换后早截止的课更早完成，晚截止的课最迟也只在原来两课一起完成的时刻结束，仍能按时完成。不断消除逆序，就能固定为这个顺序。

最大堆保存当前保留课程的时长，time 是这些时长之和。扫描到一门课时，先把它加入；若 time 不超过当前截止日，所有保留课程仍可行。若超时，就从堆中删除时长最大的一门，被删除的也可能正是刚加入的课。

删除最长课不会损失最优答案，可以用交换法证明。将尚未删除的课程按截止时间排列，当前前缀是第一次超时的前缀，任何可行方案都必须舍弃其中至少一门。设最长课为 $L$，若剩余候选中的某个最优方案保留 $L$、舍弃另一门 $S$，就用 $S$ 替换 $L$：当前课之前的每个前缀本来能全部按时完成，选其子集仍可行；从当前课起，总时长也不会增加，因为 $S$ 不比 $L$ 长。因此总能找到一个同样最优、但不选 $L$ 的方案，删除 $L$ 是安全的。

每次删除都能保留一个最优方案，剩余课程又始终可行，所以最终堆中的数量就是最多门数。一次删除也足够恢复可行：加入前的总时长不超过当前截止日，而堆中最大时长至少等于本轮新增时长，删除后总时长不会大于加入前。

解题步骤

  1. 按截止时间升序排序。
  2. 将当前时长加入总时间和最大堆。
  3. 超出当前截止时间时，弹出最长课程并扣减总时间。
  4. 返回堆中剩余课程数量。

代码实现

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();
    }
}

import (
    "container/heap"
    "sort"
)

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+1))$，排序与每门课程固定次数的堆操作。
  • 空间复杂度：$O(n)$，堆和排序工作区。

关键点总结

[!green]

  • 截止时间决定处理顺序，持续时间决定撤销对象。
  • 总时间始终等于堆内课程时长之和。
  • 恰好在截止当天完成是合法的。
  • 若某门课自身时长就超过截止日，它会在同一套加入、弹出流程中被淘汰，无需单独分支。

易错点总结

[!yellow]

  • 按时长排序套用同一逻辑：早截止课程可能被后处理而错失。
  • 超时只跳过当前课程：不能用短课替换已选长课。
  • 使用最小堆撤销：释放的时间不足，并留下更重负担。
  • 弹出后不减总时间：后续可行性判断仍使用旧值。

相似题目

题目 难度 关联与区别
502. IPO 困难 同样按可行条件排序并用堆选择，原题优先增加收益，本题超出截止时间时淘汰最长课程。
1353. 最多可以参加的会议数目 中等 同样按截止条件安排最多事件，原题每个事件只占一天，本题各课程持续时间不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/51710958
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！