区间调度

区间调度在同一资源上选择最多个互不重叠的区间。按结束时间排序，每次接受第一个兼容区间。对不带权、目标为数量最多的问题，该贪心法最优，总时间 O(n log n)。

会议开始早，不代表有利，它可能占用房间一整天。结束早的会议先释放资源，为后续请求留出空间。

区间调度如何工作

区间写成半开形式 [start, end)：时间 5 结束与时间 5 开始的会议兼容，接触但不重叠。

last_end 保存最近接受区间的结束时间。按 end 排序后逐个处理：

1. start >= last_end：接受，写 last_end = end。
2. start < last_end：拒绝，last_end 不变。

拒绝项不进入日程，所以不能改变兼容边界。

交换论证

取任意最优日程 O，把下一项与贪心选择比较。贪心在兼容项中结束最早，用它替换 O 的下一项后，后续原本能放下的区间仍能放下，数量也不变。对后缀重复，最终可把任意最优日程改成贪心日程而不损失数量。

证明栏展示一个具体 O，但论证不局限于它。因为任意最优解都能这样交换，贪心与最优解同样大。这不只是“找到四个”，还证明没有日程能选五个。

逐步演示

输入顺序：

A=[0,3)、B=[5,7)、C=[1,2)、D=[6,9)、E=[3,5)、F=[4,6)、G=[7,9)、H=[2,5)。

按结束时间、再按开始时间排序，同值保持输入顺序，得到 C, A, H, E, F, B, D, G。

1. C [1,2) 首先接受，last_end = 2。
2. A [0,3) 的开始 0 < 2，拒绝，边界仍为 2。
3. H [2,5) 的开始恰等于 2，接受，边界到 5。
4. E [3,5) 开始小于 5，拒绝。
5. F [4,6) 同样拒绝。
6. B [5,7) 接触边界，接受，边界到 7。
7. D [6,9) 开始小于 7，拒绝。
8. G [7,9) 接触边界，接受，边界到 9。

选择 C, H, B, G，保留四个，移除四个。

证明栏从另一最优日程 A, E, B, G 开始。A 换成 C，结束从 3 提前到 2，后缀仍兼容。E 换成 H，两者都结束于 5，后续也不受影响。B、G 已相同。数量仍为四，得到贪心结果。

这个输入中，按最早开始也恰好得到 A, E, B, G，不能据此证明开始时间规则正确。Long blocker 中，最早开始只能保留一个，最早结束保留七个。

移除最少区间是同一目标的另一面：minimum removals = n - maximum compatible count，对应 LeetCode 435。

画布的竖线表示 last_end。接受项进入 chosen 栏并推进边界，拒绝项展示冲突，边界保持原位。

时间与空间复杂度

已按结束时间排序时，只需 O(n) 扫描。展示代码复制输入到 ordered，并保存 chosen，空间 O(n)。数组之外的贪心状态只有 last_end，为 O(1)。

边界情况

• 空输入：返回空日程。编辑器要求至少一个区间，但步骤生成器处理空情况。
• 单区间：直接接受。
• 两两冲突：只能取一个，选择结束最早的兼容候选。
• 端点接触：[0,2) 与 [2,4) 兼容，需要 >=。
• 相同结束时间：在当前兼容候选中任取一个都不影响最大数量。本课按开始时间、稳定输入顺序打破平局。
• 带权目标：若要价值总和最大，交换只保数量，不保价值，需要带权区间 DP 等方法。

常见错误

• 按最早开始排序。 长区间可能阻挡全部后续，Long blocker 给出一比七的反例。
• 按最短持续时间。 短区间可能横在中间，挡住前后两项，不能沿用交换证明。
• 用 start > last_end。 会拒绝合法的背靠背区间。
• 拒绝后也改边界。 边界属于最后接受项，拒绝请求不能移动它。
• 混用闭区间与半开区间。 若两端都占用资源，端点相等可能冲突，比较式要匹配领域规则。
• 把证明推广到权重。 交换保留的是数量，不是任意价值总和。