区间调度贪心精讲：覆盖、不重叠与最少箭头

摘要

区间类贪心是面试中出现频率极高的一个专题，几乎每家大厂都会考到。本文深度剖析三道核心题目：LeetCode 435（无重叠区间，移除最少区间使之不重叠）、LeetCode 452（用最少数量的箭刺破气球，即最少点覆盖）和 LeetCode 56（合并区间）。这三道题乍看是三个独立问题，实则有深刻的等价性：最少移除区间数 = 总数 - 最多不重叠区间数，而最多不重叠区间数 = 最少刺破气球数。理解这两个等价变换，你才能在面试中快速识别区间类贪心，而不是硬背题目。

第 1 章区间类贪心的核心排序原则

1.1 为什么排序是区间贪心的关键

区间类问题的共同特征：给定若干区间 $[l_{i}, r_{i}]$ ，要求在某种约束下选择/合并/覆盖区间。

排序为什么关键：区间之间的”冲突”（重叠）关系依赖于起点和终点的相对顺序。如果不排序，处理每个区间时需要检查其他所有区间，导致 $O (n^{2})$ 的复杂度。排序后，处理每个区间时只需与”当前最后确定的区间”比较，降到 $O (n)$ （在排序之后）。

按哪个字段排序：这是区间贪心的关键设计决策，不同问题用不同排序基准：

问题	排序基准	原因
最多不重叠区间选择（活动选择）	按右端点升序	结束早的活动”占用时间短”，给后续留更多余地
最少箭头覆盖	按右端点升序	同上（与活动选择等价）
区间合并	按左端点升序	需要检测相邻区间是否重叠，按左端点排序后，相邻区间是”最可能合并”的候选
区间覆盖问题	按左端点升序	需要按顺序覆盖连续范围

1.2 按右端点排序的核心直觉

为什么活动选择按右端点排序而非左端点？

假设有两个活动： $A = [1, 10]$ （从 1 到 10）， $B = [5, 7]$ （从 5 到 7）。如果按左端点排序，先选 $A$ ，然后 $B$ 与 $A$ 重叠，被放弃。最终选了一个活动 $A$ 。

如果按右端点排序，先选 $B$ （结束更早），然后剩余时间 $[8, + \infty)$ 还可以容纳其他活动。 $A$ 与 $B$ 重叠，被放弃。最终选了一个活动 $B$ 。

乍看两种排序都只选了一个活动，但如果还有活动 $C = [8, 9]$ ：

按左端点排序：先选 $A$ ，再看 $C$ ， $C$ 与 $A$ 不重叠，选 $C$ ，总共 2 个
按右端点排序：先选 $B$ ，再看 $A$ （与 $B$ 重叠，跳过），再看 $C$ （与 $B$ 不重叠），选 $C$ ，总共 2 个

两种方法结果相同！但更极端的情形能说明差异：

如果还有 $D = [9, 11]$ （在 $A$ 结束前开始，在 $C$ 结束后才结束）：

按左端点排序： $A$ 结束时间 10， $D$ 开始时间 9， $D$ 与 $A$ 重叠，放弃 $D$ 。选了 { $A, C$ }，共 2 个
按右端点排序：选了 { $B, C, D$ }，共 3 个

结论：按右端点排序（选结束最早的）让已选活动的”右边界”尽可能小，给后续活动留出更多空间，从而能选更多活动。

第 2 章 LeetCode 435：无重叠区间

2.1 题目

LeetCode 435 - Non-overlapping Intervals（中等）

给定一个区间的集合 intervals，其中 intervals[i] = [starti, endi]。返回需要移除区间的最小数量，使剩余区间互不重叠。

注意：只在一点上接触的区间，例如 [1, 2] 和 [2, 3]，是不重叠的（端点相等不算重叠）。

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩余的区间没有重叠

输入: intervals = [[1,2],[1,2],[1,2]]
输出: 2
解释: 需要移除两个 [1,2] 才能使剩余的区间没有重叠

输入: intervals = [[1,2],[2,3]]
输出: 0
解释: 不需要移除任何区间

2.2 关键等价变换

直接求”最少移除数量”比较难，但通过等价变换，可以转化为更好解决的问题：

$最少移除数量 = 总区间数 - 最多不重叠区间数$

所以，最少移除区间 = 总数 - 最多能选多少个互不重叠的区间。

最多不重叠区间选择 = 活动选择问题，是贪心的经典应用（按右端点排序，每次选不与当前已选集合冲突的、结束最早的区间）。

2.3 贪心实现

public int eraseOverlapIntervals(int[][] intervals) {
    // 按右端点升序排序
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
 
    int count = 0;          // 已选的不重叠区间数量
    int lastEnd = Integer.MIN_VALUE;  // 最后一个选中区间的右端点
 
    for (int[] interval : intervals) {
        // 如果当前区间的左端点 >= 上一个选中区间的右端点，不重叠，可以选
        if (interval[0] >= lastEnd) {
            count++;
            lastEnd = interval[1];  // 更新最后一个选中区间的右端点
        }
        // 否则，当前区间与已选区间重叠，跳过（不选它）
    }
 
    // 最少移除数量 = 总数 - 最多不重叠数
    return intervals.length - count;
}

复杂度：

排序： $O (n lo g n)$
线性扫描： $O (n)$
总计： $O (n lo g n)$

2.4 交换论证证明

命题：按右端点排序后，贪心地选择不重叠的区间，得到的是最多不重叠区间集合。

证明：设贪心选了 $m$ 个区间，任意一个最优解选了 $k$ 个区间（ $k \geq m$ ，因为最优解选了最多）。

设贪心选的区间按顺序为 $g_{1}, g_{2}, ..., g_{m}$ （右端点递增），最优解选的为 $o_{1}, o_{2}, ..., o_{k}$ （右端点递增）。

引理：对所有 $t \leq m$ ，有 $g_{t} . end \leq o_{t} . end$ （贪心选的第 $t$ 个区间的右端点不大于最优解的第 $t$ 个区间的右端点）。

引理证明（归纳）：

$t = 1$ ：贪心选的第一个区间 $g_{1}$ 是所有区间中右端点最小的，因此 $g_{1} . end \leq o_{1} . end$ 。
假设 $g_{t - 1} . end \leq o_{t - 1} . end$ ，证明 $g_{t} . end \leq o_{t} . end$ ：
- 最优解的第 $t$ 个区间 $o_{t}$ 与 $o_{t - 1}$ 不重叠，即 $o_{t} . start \geq o_{t - 1} . end \geq g_{t - 1} . end$
- 所以 $o_{t}$ 与 $g_{t - 1}$ 不重叠， $o_{t}$ 是贪心可以选的候选（从 $g_{t - 1}$ 之后开始）
- 贪心选的 $g_{t}$ 是在不与 $g_{t - 1}$ 重叠的区间中，右端点最小的
- 因此 $g_{t} . end \leq o_{t} . end$

由引理，贪心选完 $m$ 个区间后， $g_{m} . end \leq o_{m} . end$ 。若 $k > m$ ，则最优解还有第 $m + 1$ 个区间 $o_{m + 1}$ ，满足 $o_{m + 1} . start \geq o_{m} . end \geq g_{m} . end$ ，所以 $o_{m + 1}$ 与 $g_{m}$ 不重叠，贪心也可以选 $o_{m + 1}$ 。这与贪心已选完 $m$ 个（不能再选）矛盾。因此 $k \leq m$ ，结合 $k \geq m$ ，得 $k = m$ 。

第 3 章 LeetCode 452：用最少数量的箭刺破气球

3.1 题目

LeetCode 452 - Minimum Number of Arrows to Burst Balloons（中等）

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 中，其中 points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，且满足 xstart ≤ x ≤ xend，则该气球会被引爆。

给你一个数组 points，返回引爆所有气球所必须射出的最小弓箭数。

输入: points = [[10,16],[2,8],[1,6],[7,12]]
输出: 2
解释: 气球可以用 2 支箭来爆破：
  在 x = 6 处射出箭，[2,8] 和 [1,6] 都会被引爆
  在 x = 11 处射出箭，[10,16] 和 [7,12] 都会被引爆

输入: points = [[1,2],[3,4],[5,6],[7,8]]
输出: 4

输入: points = [[1,2],[2,3],[3,4],[4,5]]
输出: 2

3.2 与 LeetCode 435 的等价性

关键洞察：一支箭能同时刺破多个气球，当且仅当这些气球两两都有公共点（即它们构成一个公共重叠区域）。

换句话说：一组气球能被一支箭刺破，当且仅当这组气球有公共交集（至少一个 x 坐标同时在所有气球范围内）。

等价变换：

最少箭数 = 最少的”不相交组”数 = 最大不相交区间集合的大小（其中每组气球可以被一支箭刺破，意味着组内气球两两重叠）
反过来，一组内的气球两两重叠（有公共交集），相当于在不重叠区间的”补集”上分组

等等，这个等价不太直观，让我换个角度：

最少箭数 = 最大不重叠区间集合的大小。

为什么？对任意一组”能被一支箭刺破”的气球，从该组中每个气球各选一个代表，这些代表的区间两两重叠。反过来，任意一组两两重叠的区间，可以找到一个公共点，用一支箭射穿。

所以，每支箭刺破的一组气球中，任意两个气球重叠，而不同组的气球之间不能被同一支箭刺破（即不同组的代表区间不重叠）。

最大不重叠区间集合恰好就是”每组选一个代表，各组之间不重叠”，其大小等于最少的分组数，即最少的箭数。

等价性的严格表述

设 $S$ 是最大不重叠区间集合，大小为 $k$ 。

这 $k$ 个区间两两不重叠，不能被一支箭同时刺破，所以至少需要 $k$ 支箭。

另一方面，可以按右端点排序，每次用一支箭射在当前组的最左右端点（贪心）， $k$ 支箭可以刺破所有气球。

因此最少箭数恰好是 $k$ 。

3.3 贪心实现

与 LeetCode 435 的贪心几乎完全相同，区别在于重叠的定义：

LeetCode 435：[1,2] 和 [2,3] 不重叠（端点相等不算重叠）
LeetCode 452：[1,2] 和 [2,3] 重叠（一支射在 x=2 的箭可以同时刺破两者）

public int findMinArrowShots(int[][] points) {
    // 按右端点升序排序
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    // 注意：不能用 a[1] - b[1]，因为端点可能是负数，相减可能溢出
 
    int arrows = 1;  // 至少需要一支箭
    int arrowPos = points[0][1];  // 第一支箭射在第一个气球的右端点
 
    for (int i = 1; i < points.length; i++) {
        // 如果当前气球的左端点 > 当前箭的位置，无法刺破，需要新箭
        if (points[i][0] > arrowPos) {
            arrows++;
            arrowPos = points[i][1];  // 新箭射在当前气球的右端点
        }
        // 否则，当前气球可以被当前箭刺破，不需要新箭
    }
 
    return arrows;
}

注意：排序用 Integer.compare(a[1], b[1]) 而非 a[1] - b[1]，因为端点可能是 Integer.MIN_VALUE，相减会溢出！这是面试中的常见扣分点。

与 LeetCode 435 的细节差异：

435 中 “不重叠” 的条件是 interval[0] >= lastEnd（左端等于右端视为不重叠）
452 中 “需要新箭” 的条件是 points[i][0] > arrowPos（左端严格大于，才不能被当前箭刺破；等于时当前箭恰好在边界，可以刺破）

3.4 手工演示

以 points = [[10,16],[2,8],[1,6],[7,12]] 为例：

排序后（按右端点）：[[1,6],[2,8],[7,12],[10,16]]

i	interval	arrowPos	条件	操作
初始	[1,6]	6	—	arrows=1, arrowPos=6
1	[2,8]	6	2 ⇐ 6，不需要新箭	继续
2	[7,12]	6	7 > 6，需要新箭	arrows=2, arrowPos=12
3	[10,16]	12	10 ⇐ 12，不需要新箭	继续

最终 arrows = 2，正确。

第 4 章 LeetCode 56：合并区间

4.1 题目

LeetCode 56 - Merge Intervals（中等）

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间

4.2 为什么按左端点排序

LeetCode 435 和 452 按右端点排序，而 LeetCode 56 按左端点排序。

原因：LeetCode 56 要求合并，不是选择。合并操作的目标是”把能合并的相邻区间都合并”，按左端点排序后，相邻的区间是”最可能重叠”的候选（如果一个区间的左端点在另一个区间范围内，它必然是排序后紧接着的）。

按右端点排序在合并问题中行不通——你需要知道当前区间的左端点是否在已合并范围内，这要求按左端点顺序处理。

4.3 贪心实现

public int[][] merge(int[][] intervals) {
    // 按左端点升序排序
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
 
    List<int[]> merged = new ArrayList<>();
    int[] current = intervals[0];  // 当前正在构建的合并区间
 
    for (int i = 1; i < intervals.length; i++) {
        int[] next = intervals[i];
 
        if (next[0] <= current[1]) {
            // 当前区间与 current 重叠（next 的左端点在 current 范围内）
            // 合并：更新 current 的右端点为两者中更大的
            current[1] = Math.max(current[1], next[1]);
        } else {
            // 不重叠：将 current 加入结果，开始新的合并区间
            merged.add(current);
            current = next;
        }
    }
 
    // 将最后一个合并区间加入结果
    merged.add(current);
 
    return merged.toArray(new int[0][]);
}

为什么合并是 current[1] = Math.max(current[1], next[1])：

当 next[0] <= current[1] 时（next 与 current 重叠），合并后的区间左端点是 current[0]（排序后 next[0] >= current[0]，所以 current 的左端点更小），右端点是 max(current[1], next[1])（两者中更大的）。

需要用 max 而非直接取 next[1]，是因为可能存在 next 完全包含在 current 内（next[1] <= current[1]）的情形，此时合并后右端点仍是 current[1]，不能缩小。

4.4 手工演示

以 [[1,3],[2,6],[8,10],[15,18]] 为例（已按左端点排序）：

i	next	current	条件	操作
初始	—	[1,3]	—	—
1	[2,6]	[1,3]	2⇐3，重叠	current=[1,max(3,6)]=[1,6]
2	[8,10]	[1,6]	8>6，不重叠	add [1,6]，current=[8,10]
3	[15,18]	[8,10]	15>10，不重叠	add [8,10]，current=[15,18]
结束	—	[15,18]	—	add [15,18]

结果：[[1,6],[8,10],[15,18]]，正确。

第 5 章三道题深度对比与模式总结

5.1 三道题的等价性网络

LeetCode 435（最少移除）
   = 总数 - 最多不重叠
   
最多不重叠（活动选择）
   = LeetCode 452 的最少箭数
（同一贪心，只是重叠定义略有差异）

LeetCode 56（合并区间）
   = 将所有重叠区间合并，结果区间数 = 最大不重叠组数
（最终的合并区间数 = 最少箭数，如果把重叠定义统一）

5.2 排序基准选择原则（总结）

目标	排序基准	理由
选最多不重叠区间（435 / 活动选择）	按右端点升序	结束早的区间给后续留更多空间（交换论证可证）
射穿所有区间（452）	按右端点升序	等价于活动选择，同样的贪心
合并所有重叠区间（56）	按左端点升序	需要检测”相邻区间是否重叠”，左端点排序后相邻即相近

5.3 重叠定义的细节

题目	重叠定义	`[1,2]` 和 `[2,3]`	条件表达式
LeetCode 435	端点相等不算重叠	不重叠	`interval[0] >= lastEnd`
LeetCode 452	端点相等算重叠	重叠（箭在 x=2 可同时穿过）	`points[i][0] > arrowPos`
LeetCode 56	端点相等算重叠	重叠（合并为 [1,3]）	`next[0] <= current[1]`

这个细节区别在面试中很容易混淆，建议在脑海中对应具体的场景理解，而不是死记 > 还是 >=。

5.4 区间类贪心的通用解题步骤

明确”重叠”的定义：端点相等是否算重叠？看题意
选择排序基准：选/覆盖问题用右端点，合并问题用左端点
维护关键状态：通常是”上一个已确定区间的右端点”
线性扫描：对每个新区间，判断是否与已确定区间重叠，做对应操作（选或合并或跳过）

第 6 章本文核心结论

三道题通过等价变换相互关联：435 = 总数 - 活动选择，452 = 活动选择（重叠定义略不同），56 = 合并所有组。理解等价性，就能在面试中遇到新的区间变体时快速定位到已知模式。
排序基准决定一切：选/覆盖问题按右端点（让已选区间尽早结束），合并问题按左端点（相邻区间是重叠候选）。这一原则对绝大多数区间贪心题有效。
重叠定义的 >= vs >：端点相等算不算重叠，取决于物理场景。气球题等于算重叠（箭可以在端点刺穿），区间不重叠题等于不算重叠（两个活动在同一时刻结束/开始是允许的）。
排序的溢出陷阱：排序 Comparator 用 Integer.compare(a, b) 而非 a - b，避免整数溢出。这是面试中容易扣分的实现细节。
区间类贪心的时间复杂度：排序主导， $O (n lo g n)$ ，线性扫描 $O (n)$ ，总体 $O (n lo g n)$ 。

汀的知识碎片

文章导航

08 区间调度贪心精讲：覆盖、不重叠与最少箭头

区间调度贪心精讲：覆盖、不重叠与最少箭头

摘要

第 1 章区间类贪心的核心排序原则

1.1 为什么排序是区间贪心的关键

1.2 按右端点排序的核心直觉

第 2 章 LeetCode 435：无重叠区间

2.1 题目

2.2 关键等价变换

2.3 贪心实现

2.4 交换论证证明

第 3 章 LeetCode 452：用最少数量的箭刺破气球

3.1 题目

3.2 与 LeetCode 435 的等价性

3.3 贪心实现

3.4 手工演示

第 4 章 LeetCode 56：合并区间

4.1 题目

4.2 为什么按左端点排序

4.3 贪心实现

4.4 手工演示

第 5 章三道题深度对比与模式总结

5.1 三道题的等价性网络

5.2 排序基准选择原则（总结）

5.3 重叠定义的细节

5.4 区间类贪心的通用解题步骤

第 6 章本文核心结论

On this page

汀的知识碎片

文章导航

08 区间调度贪心精讲：覆盖、不重叠与最少箭头

区间调度贪心精讲：覆盖、不重叠与最少箭头

摘要

第 1 章 区间类贪心的核心排序原则

1.1 为什么排序是区间贪心的关键

1.2 按右端点排序的核心直觉

第 2 章 LeetCode 435：无重叠区间

2.1 题目

2.2 关键等价变换

2.3 贪心实现

2.4 交换论证证明

第 3 章 LeetCode 452：用最少数量的箭刺破气球

3.1 题目

3.2 与 LeetCode 435 的等价性

3.3 贪心实现

3.4 手工演示

第 4 章 LeetCode 56：合并区间

4.1 题目

4.2 为什么按左端点排序

4.3 贪心实现

4.4 手工演示

第 5 章 三道题深度对比与模式总结

5.1 三道题的等价性网络

5.2 排序基准选择原则（总结）

5.3 重叠定义的细节

5.4 区间类贪心的通用解题步骤

第 6 章 本文核心结论

On this page

第 1 章区间类贪心的核心排序原则

第 5 章三道题深度对比与模式总结

第 6 章本文核心结论