引言 (Introduction)
区间调度（Interval Scheduling）是贪心算法最经典、也最能彰显其威力的应用领域。核心问题极其简洁：给出一组区间，从中选出最多的互不重叠的区间。表面上是一个简单的"选或不选"问题，实际上却暗藏反直觉的陷阱。
本文是本系列第二篇，在上一篇理论基础上，将聚焦于区间贪心的建模套路。核心任务只有一个：理解为什么贪心策略要这样选，以及如何严格证明它。
1. 经典区间调度问题
1.1 问题陈述
给定 $n$ 个区间 $[s_i, e_i)$，选择最大数量的互不重叠的区间。
1.2 为什么按结束时间排序？
直觉上，我们可以考虑三种贪心策略：
| 排序依据 | 策略 | 结果 |
|---|---|---|
| 按开始时间 $s_i$ 升序 | 优先选开始早的 | ❌ 错误：一个超长区间会阻挡后续所有区间 |
| 按持续时长 $e_i-s_i$ 升序 | 优先选短的 | ❌ 错误：两侧不重叠的短区间可能因中间的短区间而被放弃 |
| 按结束时间 $e_i$ 升序 | 优先选结束早的 | ✅ 正确 |
直觉解释：早结束的区间为后面的区间留出了最多的时间空间（或者说最大化了剩余资源）。选择当前能选的、结束时间最早的区间，是一个"利他"的选择——自己占用的时间资源最少。
按开始时间排序（错误）：
[0================9]
[1==2] [3==4] [5==6] [7==8]
贪心只能选 1 个（第一个超长区间），实际可以选 4 个。
按结束时间排序（正确）：
[1==2] [3==4] [5==6] [7==8]
[0================9]
贪心选出前 4 个短区间，最优解。
1.3 交换论证——严格证明
定理：按结束时间升序贪心选取的策略能够选出最大数量的互不重叠区间。
证明（交换论证）：
令贪心解为 $G = \{g_1, g_2, \ldots, g_k\}$，其中 $g_1$ 是结束时间最早的区间，$g_2$ 是在 $g_1$ 结束后结束时间最早的区间，依此类推。
假设存在一个更优解 $O = \{o_1, o_2, \ldots, o_m\}$，其中 $m > k$，且 $O$ 中的区间也按结束时间升序排列。
断言：对于所有 $r \le k$，有 $e(g_r) \le e(o_r)$。
对 $r$ 使用数学归纳法：
- $r = 1$：$g_1$ 是所有区间中结束时间最早的，所以 $e(g_1) \le e(o_1)$ 显然成立。
- 归纳步：假设 $e(g_{r-1}) \le e(o_{r-1})$。对于第 $r$ 步，$O$ 中的 $o_r$ 必须满足 $s(o_r) \ge e(o_{r-1})$（与前一区间不重叠）。而贪心选择的 $g_r$ 是所有满足 $s \ge e(g_{r-1})$ 的区间中结束时间最早的。由于 $e(g_{r-1}) \le e(o_{r-1})$，满足 $s \ge e(g_{r-1})$ 的区间包含满足 $s \ge e(o_{r-1})$ 的区间。因此 $e(g_r) \le e(o_r)$。
结论：$e(g_k) \le e(o_k)$。由于 $m > k$，$o_{k+1}$ 的起始时间 $s(o_{k+1}) \ge e(o_k) \ge e(g_k)$。这意味着 $o_{k+1}$ 与 $G$ 中所有区间不重叠，贪心算法应该在 $g_k$ 之后继续选择 $o_{k+1}$（或结束更早的区间），这与贪心算法停止于第 $k$ 步矛盾。因此不存在 $m > k$ 的可行解，贪心解即为最大。
这个证明的结构是区间贪心正确性证明的标准模板，后文的每道题都将沿用这一思路。
2. LeetCode 435：无重叠区间
题目：给定区间集合 intervals，求需要移除的最小区间数，使得剩余区间互不重叠。
2.1 问题转化
「最少移除数」= $n$ − 「最多保留数」——后者正是经典区间调度问题。
2.2 完整代码
from typing import List
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
# 按结束时间升序
intervals.sort(key=lambda x: x[1])
count = 1 # 至少选第一个
last_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= last_end: # 不重叠
count += 1
last_end = end
return len(intervals) - count
复杂度：排序 $O(n \log n)$，贪心扫描 $O(n)$。空间 $O(1)$（排序可能用 $O(\log n)$ 栈空间）。
2.3 为什么不能按开始时间排序？
如果按开始时间排序，选择「起始最早的」会选中一个可能极长的区间，把后续所有区间全部挡住。一个具体反例：
intervals = [[1, 100], [2, 3], [4, 5]]
按开始时间：选中 [1,100]，丢弃 [2,3] 和 [4,5] → 移除 2 个
按结束时间：选中 [2,3] 和 [4,5] → 移除 1 个 ✓
3. LeetCode 452：用最少数量的箭引爆气球
题目：气球在水平轴上占据区间 [x_start, x_end]。一支箭从 $x$ 坐标垂直射出，可以引爆所有 x_start ≤ x ≤ x_end 的气球。求引爆所有气球所需的最少箭数。
3.1 问题建模
这与区间调度恰好对偶：区间调度是「选最多的互不重叠区间」，而本题是「找最少的点，使得每个区间至少包含一个点」。
贪心策略：按结束坐标升序排列，在第一个气球的结束位置射一箭（尽可能射中更多后续气球），所有被射中的气球跳过，重复此过程。
气球： [1......6]
[2.........8]
[7........12]
[10........16]
箭1 在 x=6：引爆 [1,6] 和 [2,8]
箭2 在 x=12：引爆 [7,12] 和 [10,16]
共 2 支箭
3.2 完整代码
from typing import List
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x: x[1]) # 按结束坐标升序
arrows = 1
arrow_pos = points[0][1] # 第一支箭的位置
for start, end in points[1:]:
if start > arrow_pos: # 当前箭射不中这个气球
arrows += 1
arrow_pos = end # 在这个气球的结束位置射一箭
return arrows
复杂度：时间 $O(n \log n)$，空间 $O(1)$。
3.3 与区间调度的对偶关系
| 问题 | 目标 | 选择标准 |
|---|---|---|
| 区间调度（435 的正面） | 最大化保留区间数 | 选互不重叠的区间 |
| 射气球（452） | 最小化点数 | 在尽可能靠右的位置放点 |
两者都按结束时间排序，但区间调度是"跳着选区间"，射气球是"箭尽可能晚射"——箭头尽量向右，以覆盖更多重叠的气球。
4. LeetCode 56：合并区间
题目：合并所有重叠的区间，返回不重叠的区间列表。
4.1 贪心策略
这道题的策略与前两题不同：按开始时间排序，而非结束时间。原因是合并操作需要从左到右处理，每次遇到一个新区间，要么与当前区间合并（重叠），要么当前区间"封存"、开始一个新区间。
4.2 完整代码
from typing import List
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0]) # 按开始时间升序
merged: List[List[int]] = [intervals[0]]
for start, end in intervals[1:]:
last = merged[-1]
if start <= last[1]: # 重叠 → 合并
last[1] = max(last[1], end)
else: # 不重叠 → 新起一段
merged.append([start, end])
return merged
复杂度：时间 $O(n \log n)$，空间 $O(n)$（返回结果所需）。
4.3 为什么本题按开始时间排序？
合并区间需要维护「当前正在构建的区间」的状态动态变化。按开始时间排序确保我们能按从左到右的顺序处理，每个新区间进入时只需与当前区间比较——它不可能与更早的已封存区间重叠（因为开始时间递增，而早的区间已经封存）。这是一个典型的在线处理贪心模式。
5. 区间贪心的统一框架
回顾三道题，可以发现区间贪心的两条核心分支：
区间问题
├── 按结束时间排序（最大化"剩余资源"）
│ ├── 选最多的区间（活动选择、435）
│ └── 选最少的点（射气球 452——对偶问题）
│
└── 按开始时间排序（从左到右处理）
└── 合并重叠（56）
判断标准：
- 如果目标与「选择/保留多少区间」有关 → 按结束时间排序。
- 如果目标与「构建/合并新区间」有关 → 按开始时间排序。
结论 (Conclusion)
本文攻克了贪心算法中最经典的区间调度领域，核心收获有三：
- 按结束时间排序的正确性——通过交换论证严格证明，而非仅凭直觉。
- 区间选择与区间覆盖的对偶性——435 和 452 看似相反，实则共享同一套排序逻辑。
- 按开始 vs 按结束的判断准则——合并用开始，选择用结束。
下一篇将进入贪心算法的进阶领域：Huffman 编码的构造与最优性证明、分数背包、以及 Dijkstra 最短路径中隐藏的贪心思想。我们也将完成全系列的知识复盘。
下一篇预览：进阶贪心——Huffman 编码、分数背包、Dijkstra 的贪心本质（LeetCode 621、767、134）。