LeetCode 435. 无重叠区间——区间调度贪心的最优子结构证明
LeetCode 435. 无重叠区间——区间调度贪心的最优子结构证明
适读人群：Java中级及以上工程师、准备算法面试的同学 | 阅读时长：约25分钟 | 难度：中等
开篇故事
工作第八年，我经历了一次特别难忘的面试。对方是一家头部互联网公司，面试官是个30来岁的年轻技术总监，开口就问了一道看似简单的题：会议室调度——给一堆会议的时间段，怎么让同一个会议室接受尽可能多的会议？
我当时觉得这不就是个简单的贪心吗？按结束时间排序，每次选结束最早且不冲突的会议。但面试官追问：为什么按结束时间排序而不是开始时间？为什么不按会议时长排序？你能不能给我一个严格的数学证明？如果我要移除最少数量的区间使得区间互不重叠，这道题和会议室调度有什么关系？
这几个追问让我意识到，我其实并没有真正理解这道题。我只是"背"了一个结论，没有"懂"它为什么对。这次面试给我上了很深刻的一课——算法面试不只是考你会不会写代码，更考你有没有真正理解算法背后的数学原理。
今天我们就把 LeetCode 435 彻底搞清楚。不光要给出正确代码，还要把为什么按结束时间排序是正确的、为什么不能按开始时间或时长排序、最优子结构是什么，都讲透彻。
一、题目解析
题目描述： 给你一个区间的集合 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（移除两个后只剩一个）
- 输入：intervals = [[1,2],[2,3]]，输出：0（已经互不重叠，端点相等不算重叠）
关键约束解析： 端点相等时不算重叠（[1,2]和[2,3]，它们只在点2上接触，这被视为"非重叠"）。这个细节很重要，它决定了代码中判断不重叠的条件是 >= 而不是 >。
问题转化视角（关键思路）：
"移除最少区间使其不重叠"等价于"保留最多不重叠区间"，然后用总数减去保留数。这个转化非常重要：
最少移除数 = 总区间数 - 最多不重叠区间数
为什么要做这个转化？因为"保留最多不重叠区间"是一个经典的"区间调度最大化问题"（Activity Selection Problem），有成熟的贪心算法。而"移除最少区间"的思维路径更复杂，直接处理不如先转化。
最优子结构分析： 如果区间 I1, I2, ..., Ik 是最优的不重叠区间集合（按结束时间排序），去掉第一个区间 I1，剩下的 k-1 个区间必然是"在时间 end(I1) 之后的所有可用区间中"最优的不重叠集合。换句话说，大问题的最优解包含了子问题的最优解，这正是最优子结构性质。
二、解法一：动态规划（理解最优子结构）
思路详解
将每个区间看作一个"事件"，定义 dp[i] 为以第 i 个区间结尾（按结束时间排序后）的最多不重叠区间数量。
状态转移方程：dp[i] = max(dp[j] + 1)，其中 j < i 且 intervals[j][1] <= intervals[i][0]（j 的结束时间不超过 i 的开始时间，即 j 和 i 不重叠，注意端点相等时不重叠所以是 <=）。
基础情况：dp[i] = 1（每个区间自身就是一个长度为1的不重叠集合）。
最终答案：intervals.length - max(dp[i])。
这个 DP 解法帮助我们理解问题的最优子结构，但 O(n²) 的时间复杂度在 n 很大时不可接受，这就催生了更高效的贪心解法。
代码实现
import java.util.Arrays;
public class Solution_DP {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
int n = intervals.length;
// 按结束时间排序，使得 dp 的状态转移有意义
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
// dp[i] = 以第i个区间结尾的最多不重叠区间数
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
// 端点相等不算重叠，所以条件是 intervals[j][1] <= intervals[i][0]
if (intervals[j][1] <= intervals[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int maxKeep = 0;
for (int d : dp) maxKeep = Math.max(maxKeep, d);
return n - maxKeep;
}
}复杂度分析
- 时间复杂度： O(n²)，双重循环，每个区间与之前所有区间比较。排序额外 O(n log n)，但被 O(n²) 掩盖。
- 空间复杂度： O(n)，dp 数组。
- 局限性： 当 n = 10^5 时超时。DP 解法的价值在于揭示最优子结构，为理解贪心正确性提供基础。
三、解法二：贪心——为什么不能按开始时间排序
暴力反例分析
很多同学的直觉是按开始时间排序，每次选开始最早的不冲突区间。我们用一个具体的反例来说明为什么这是错的。
反例构造： 区间列表：[1, 100], [2, 3], [4, 5], [6, 7]
按开始时间排序后的顺序：[1,100], [2,3], [4,5], [6,7]
"按开始时间贪心"的决策过程：
- 选 [1,100]（开始最早），设为当前选中区间。
- [2,3] 的开始时间 2 在 100 之前，与 [1,100] 重叠，跳过。
- [4,5] 的开始时间 4 在 100 之前，与 [1,100] 重叠，跳过。
- [6,7] 的开始时间 6 在 100 之前，与 [1,100] 重叠，跳过。
- 最终只保留 1 个区间，需要移除 3 个。
但最优解是保留 [2,3], [4,5], [6,7] 三个不重叠区间，只需移除 [1,100] 一个。
按开始时间排序的根本问题在于：一个开始时间很早但持续时间很长的区间，会"霸占"大量时间段，导致后续很多区间无法被选入。它虽然开始得早，但结束得晚，为后续区间留下的空间很少。
为什么不能按区间长度排序
反例： 区间：[1,2], [2,4], [3,5], [4,6]
"按长度贪心"选 [1,2]，再选 [2,4]（不重叠），跳过 [3,5]（与[2,4]重叠），选 [4,6]（不重叠），共3个。
虽然这个例子碰巧得到了正确答案，但区间长度与"为后续区间留下多少空间"没有直接关系。可以很容易构造出按长度贪心失败的反例。区间长度是一个"全局"属性，而我们真正需要的是"结束时间"这个"局部右边界"属性。
按结束时间排序的本质
结束时间代表一个区间对后续区间的"影响范围"：结束时间越早，这个区间占用的时间越少，为后续区间留下的空间越多。
贪心策略的核心就是：每次选择结束时间最早的不冲突区间，让每一步的决策为后续决策留下最多的可能性。这就是"贪心选择属性"：每次局部最优（选结束最早的），不会使全局最优变差。
四、解法三：按结束时间贪心（最优解）
算法思路详解
区间调度问题（Activity Selection Problem）的标准贪心策略：
每次从所有与已选区间不冲突的区间中，选择结束时间最早的那个区间。
排序之后，这个过程等价于：维护一个变量 end（已选区间的最晚结束时间），遍历按结束时间排序的区间，如果当前区间的开始时间 >= end（不冲突，含端点相等），则选入，更新 end；否则跳过（不选入，即移除）。
正确性证明（归纳论证）
定理：贪心算法（按结束时间排序）得到的最多不重叠区间数等于最优解的数量。
证明（通过归纳论证"贪心不落后于最优"）：
设最优解为 OPT = {j1, j2, ..., jm}（按结束时间排序），贪心解为 GREEDY = {i1, i2, ..., ik}（按贪心顺序选取）。
引理（关键性质）： 对所有 t = 1, 2, ..., 最小值(k,m)，贪心的第 t 次选择的结束时间不晚于最优解的第 t 次选择的结束时间，即 end(it) <= end(jt)。
证明引理（数学归纳法）：
基础步骤（t=1）：贪心第一步选择所有区间中结束时间最早的 i1，而最优解第一步选择 j1，显然 end(i1) <= end(j1)（因为 i1 是全局结束时间最早的）。
归纳步骤：假设 end(it) <= end(jt) 成立，考虑 t+1 步。在最优解中，jt+1 满足 start(jt+1) >= end(jt)（OPT 中相邻区间不重叠）。由于 end(it) <= end(jt)，所以 start(jt+1) >= end(jt) >= end(it)，这意味着 jt+1 与 it 也不重叠，即 jt+1 是贪心第 t+1 步的合法候选区间。贪心选的 it+1 是所有合法候选中结束时间最早的，所以 end(it+1) <= end(jt+1)，归纳成立。
由引理推结论： 引理告诉我们，贪心在每一步的结束时间都不晚于最优解的对应步。因此 k >= m（否则，如果 k < m，OPT 中还有 jk+1，其 start(jk+1) >= end(jk) >= end(ik)，即 jk+1 与 ik 不重叠，贪心还可以选更多，矛盾）。结合贪心是可行解（k <= m），有 k = m，贪心解等于最优解。
代码实现
import java.util.Arrays;
public class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) return 0;
// 按结束时间升序排序，使用安全的比较器防止整数溢出
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
int count = 1; // 贪心保留的区间数，至少保留第一个
int end = intervals[0][1]; // 当前已选区间的最晚结束时间
for (int i = 1; i < intervals.length; i++) {
// 当前区间开始时间 >= 上一个选中区间结束时间，不重叠（端点相等也不重叠）
if (intervals[i][0] >= end) {
count++;
end = intervals[i][1]; // 更新最晚结束时间
}
// 否则当前区间与已选区间重叠，跳过（即"移除"它）
}
// 最少移除数 = 总数 - 最多保留数
return intervals.length - count;
}
}Mermaid 图：区间调度贪心过程
复杂度分析
- 时间复杂度： O(n log n)，排序主导，贪心扫描 O(n)。整体是 O(n log n)。
- 空间复杂度： O(1)（不含排序栈空间）。
五、举一反三
区间类贪心题的通用框架
区间类问题是算法竞赛和面试中的常见题型，掌握下面这个通用框架可以快速解决大多数区间贪心题：
// 区间调度最大化（保留最多不重叠区间）
public int maxNonOverlapping(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // 按结束时间排序！
int count = 0, end = Integer.MIN_VALUE;
for (int[] interval : intervals) {
if (interval[0] >= end) { // 开始时间 >= 上一个结束时间
count++;
end = interval[1];
}
}
return count;
}这个框架的核心是"按结束时间排序，贪心保留结束最早的不冲突区间"。
相关题目分析：
- LeetCode 452. 用最少数量的箭引爆气球： 区间贪心变体，按右边界排序，选最少的"穿透点"使所有区间都被穿过。本质上是求最少"覆盖集"，与本题互为对偶。
- LeetCode 56. 合并区间： 目标是合并重叠区间，按开始时间排序（注意这里是开始时间，不是结束时间）。两道题的排序维度不同，是因为目标不同。
- LeetCode 986. 区间列表的交集： 两个有序区间列表求交集，双指针，每次取较早结束的区间向前推进。
关键区分：何时按开始时间，何时按结束时间？
这是很多人混淆的地方，记住下面的规律：
按结束时间排序的场景：目标是选取尽可能多的不重叠区间（本题），或找最少的"点"覆盖所有区间（LeetCode 452）。核心是"尽早结束，为后续腾空间"。
按开始时间排序的场景：目标是合并重叠区间（LeetCode 56），或找最少的区间覆盖一个范围（LeetCode 1024）。核心是"从左到右扫描，处理连续重叠"。
六、踩坑实录
坑一：排序比较器用减法导致整数溢出
// 危险写法：当 a[1] 为 Integer.MAX_VALUE，b[1] 为负数时溢出
Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // 可能溢出！
// 安全写法
Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));这道题区间端点值可以任意大，用减法做比较器是一个典型的整数溢出陷阱。在实际项目中这样写更是灾难。我有一次在测试环境跑了很久的奇怪 bug，最后定位到就是比较器溢出。从此之后我的习惯是：所有比较器一律用 Integer.compare，绝不用减法。
坑二：区间端点相等时的边界判断
题目明确说"只在一点上接触的区间是非重叠的"，所以不重叠的判断条件是 intervals[i][0] >= end 而不是 > end。如果写成严格大于，会把恰好首尾相接的情况（如 [1,2] 和 [2,3]）错误地判定为重叠，导致多移除区间。
这种端点相等的边界问题在区间类题目中非常常见，每次做区间题都要仔细确认题目对"重叠"的定义，然后对应选择 > 还是 >=。
坑三：返回的是移除数而不是保留数
这道题问的是"最少移除几个"，而贪心直接算出的是"最多保留几个"。最少移除数 = 总区间数 - 最多保留数。别忘了最后的转换。我第一次提交就直接返回了 count（保留数），WA 了之后才反应过来。
坑四：空数组的边界处理
当 intervals 为空时，直接访问 intervals[0] 会 ArrayIndexOutOfBoundsException。要在开头加上边界判断 if (intervals.length == 0) return 0;。这类边界判断在面试中也是必须要考虑的，体现了工程思维的严谨性。
坑五：混淆区间调度和区间覆盖
区间调度（本题）：选最多的互不重叠区间，贪心按结束时间排序。
区间覆盖（LeetCode 1024 视频拼接）：用最少的区间覆盖 [0, T]，贪心按开始时间排序，每次选开始时间在当前覆盖边界内且结束时间最远的区间。
这两类题的贪心方向恰好相反，一个"贪早结束"，一个"贪晚结束"，不要把两类题的策略混用。
坑六：忘记初始化 count = 1
贪心代码中，count 从 1 开始（第一个区间总是被保留，因为没有比它更早结束的区间了），for 循环从 i=1 开始。如果 count 初始化为 0，for 循环从 i=0 开始，结果也对，但这样写的意图不如 count=1 加 i=1 的写法清晰。
七、总结
LeetCode 435 是区间类贪心的经典题，核心在于理解为什么要按结束时间排序，以及如何用最优子结构和归纳论证来证明贪心正确性。
三个关键认知总结：
第一，"移除最少"等价于"保留最多"，这个等价转换是解题的第一步，也体现了算法思维中的"等价转换"技巧。很多时候，正面攻击一个问题不如先把它转化为等价但更好处理的形式。
第二，按结束时间贪心的本质是：每次为剩余时间段留尽可能多的"空余"。这是一种"机会成本最小化"的策略——每次的选择尽量少消耗未来的可能性。
第三，归纳证明"贪心在每一步的结束时间都不晚于最优解的对应步"，是严格论证贪心正确性的方法。这个证明思路对后续的区间调度变体（如引爆气球）同样适用，理解它就理解了整个区间贪心的证明方法论。
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 动态规划 | O(n²) | O(n) | 理解最优子结构，n 小时可用 |
| 贪心（按结束时间） | O(n log n) | O(1) | 实际面试和生产代码推荐 |