图解实验室 / 入门进阶 · 15 分钟 · 算法
区间调度图解：为什么先选最早结束的活动？
同一条时间轴上，选尽可能多的互不冲突活动。不是先开始、不是先选最长，而是让每次选择尽早为后面腾出时间。
① 保留原始身份，看清时间占用
绿色粗线与 ✓ = 已选；斜线纹与 × = 冲突跳过；灰蓝 = 尚未处理。实心点为开始，空心点为结束；结束时刻允许下一项开始。ID 始终对应输入行。
步骤 0/7。当前按输入顺序显示；每条横线是真实时间区间，尚未选择任何活动。
选择条件：尚未选择，或 start ≥ lastEnd。当前 lastEnd = null（没有已选活动）；已选数量 = 0。
// 每个活动保留原输入 ID；本题只最大化数量
let lastEnd = null;
const selected = [];← / → 单步，Home / End 首尾；输入与滚动区域保留原按键。无自动播放，减少动画偏好关闭排序和边界移动。空输入、负时间是教学扩展。仅求最大数量，不适用于带权收益、多个观众或区间覆盖。数据不离开本页。
自测：结束时间相同，选更早开始的活动一定更好吗？
不一定需要更早开始：在都能接上当前安排时，同样的结束时间给后续留下相同空间。本页用开始时间、ID 打破平局只是为了复现实验；正确性的关键是优先最早结束。
看完图，带走这些结论
要选出最多个互不重叠活动，先按结束时刻升序排列。依次检查每个区间：尚未选过，或 start≥lastEnd 时接受，并令 lastEnd=end；否则跳过。最早结束的选择给后续留下最多时间。这里最大化数量，不是总时长或权重。
适用条件与边界
每项活动占用 [start,end)，start<end；前一项结束恰等于后一项开始时可以衔接。原始输入索引是稳定 ID，重复区间仍是不同活动。本页教学模型支持 0–8 项稠密数组，端点为 −9…12 的整数，负零按0处理；空输入返回0。官方 CSES 1629 的 n≥1、时间均为正数，空输入与负时间只是教学扩展。
始终保持的规律
按结束时刻扫描时，已选活动互不重叠，lastEnd 是最后一项的结束时刻；每个被接受的最早结束选择都可出现在某个最优安排中。
逐步例子
- 默认输入 ID0=[1,10)、ID1=[2,3)、ID2=[3,4)、ID3=[4,6)、ID4=[5,7)、ID5=[6,8)。区间的水平长度表示持续时间，纵向行只用于排版，不表示另一维时间。
- 按 end、start、ID 升序排序，顺序为 [1,2,3,4,5,0]。后两项只是确定同结束时刻的展示顺序；最优数量不依赖这种平局规则。
- 先选 ID1=[2,3)，lastEnd=3。ID2 从3开始，满足3≥3，故可以接上；选择后 lastEnd=4。不能把相等端点错判成冲突。
- 接着选 ID3=[4,6)，跳过 ID4=[5,7)，因为5<6。拒绝不会改变 lastEnd；再选 ID5=[6,8)，最后跳过 ID0=[1,10)。最终选择 [1,2,3,5]，共4项。
- 交换论证：设某个最优安排的第一项为o，全体活动中结束最早的为g，则g.end≤o.end。把o换成g，后续所有活动仍能接上，而且数量不减。于是至少存在一个最优安排以g开头。
- 固定g后，只看 start≥g.end 的剩余活动，原问题缩小为同样的最大数量问题。反复交换/归纳，得到整套贪心安排最优；这不是仅凭几个例子猜规则。
- 按开始最早不可靠：对 [1,10)、[2,3)、[3,4)，先选 [1,10) 只能得到1项，按结束最早可以选后两项得到2项。并非任何看似合理的排序都正确。
- 重复区间 [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表示尚未选取，首项直接接受。