# 区间调度图解：为什么先选最早结束的活动？

在同一条 SVG 时间轴上移动活动区间，按结束时刻排序并逐项选择；用可用时间边界、首尾相接和反例说明最大数量的贪心策略。

原文 / Canonical: https://crazycloud.cc/learn/interval-scheduling
作者: crazycloudcc
首次发布: 2026-11-03
更新: 2026-11-03

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

要选出最多个互不重叠活动，先按结束时刻升序排列。依次检查每个区间：尚未选过，或 start≥lastEnd 时接受，并令 lastEnd=end；否则跳过。最早结束的选择给后续留下最多时间。这里最大化数量，不是总时长或权重。

## 适用条件与边界

每项活动占用 [start,end)，start<end；前一项结束恰等于后一项开始时可以衔接。原始输入索引是稳定 ID，重复区间仍是不同活动。本页教学模型支持 0–8 项稠密数组，端点为 −9…12 的整数，负零按0处理；空输入返回0。官方 CSES 1629 的 n≥1、时间均为正数，空输入与负时间只是教学扩展。

## 不变量

按结束时刻扫描时，已选活动互不重叠，lastEnd 是最后一项的结束时刻；每个被接受的最早结束选择都可出现在某个最优安排中。

## 逐步例子

1. 默认输入 ID0=[1,10)、ID1=[2,3)、ID2=[3,4)、ID3=[4,6)、ID4=[5,7)、ID5=[6,8)。区间的水平长度表示持续时间，纵向行只用于排版，不表示另一维时间。
2. 按 end、start、ID 升序排序，顺序为 [1,2,3,4,5,0]。后两项只是确定同结束时刻的展示顺序；最优数量不依赖这种平局规则。
3. 先选 ID1=[2,3)，lastEnd=3。ID2 从3开始，满足3≥3，故可以接上；选择后 lastEnd=4。不能把相等端点错判成冲突。
4. 接着选 ID3=[4,6)，跳过 ID4=[5,7)，因为5<6。拒绝不会改变 lastEnd；再选 ID5=[6,8)，最后跳过 ID0=[1,10)。最终选择 [1,2,3,5]，共4项。
5. 交换论证：设某个最优安排的第一项为o，全体活动中结束最早的为g，则g.end≤o.end。把o换成g，后续所有活动仍能接上，而且数量不减。于是至少存在一个最优安排以g开头。
6. 固定g后，只看 start≥g.end 的剩余活动，原问题缩小为同样的最大数量问题。反复交换/归纳，得到整套贪心安排最优；这不是仅凭几个例子猜规则。
7. 按开始最早不可靠：对 [1,10)、[2,3)、[3,4)，先选 [1,10) 只能得到1项，按结束最早可以选后两项得到2项。并非任何看似合理的排序都正确。
8. 重复区间 [1,3)、[1,3)、[3,4) 只能选其中一个 [1,3) 再接 [3,4)，共2项。负时间用“尚未选取”状态初始化；若把 lastEnd 写死为0，会漏掉合法负时间活动。

## 排序、扫描与教学轨迹

通常排序需要 O(n log n) 时间，再线性扫描 O(n)；保存所选活动 O(n) 空间。若只求数量，排序之后的扫描状态为 O(1)。本页为保留每一步的排序、已选与跳过集合而复制轨迹，额外时间与空间为 O(n²)，不能把整套动画当作常数空间实现。区间值有界只为图形可读性，不是算法上限。

## 常见误区

- 按最早开始或最长持续时间排序，误以为也总是最优
- 用 start>lastEnd 拒绝首尾相接的活动
- 跳过冲突项时也更新 lastEnd
- 把坐标轴从0起画当作所有输入都非负
- 去掉重复区间后丢失输入身份，或同时接受重叠重复项
- 把最大数量结论直接推广到加权收益、多位观众或区间覆盖

## 自测

[−4,−2)、[−2,−1)、[−3,2) 最多选几项？如果 lastEnd 初始为0会怎样？

可选前两项，共2项，端点−2相等可衔接。lastEnd=0会错误跳过所有开始时刻为负的活动；本页以null表示尚未选取，首项直接接受。

## 参考资料

- [CSES 1629：Movie Festival（最大数量、允许首尾衔接）](https://cses.fi/problemset/task/1629/)

[返回图解实验室](https://crazycloud.cc/learn)