LeetCode 435. 无重叠区间

题目思路

给定若干区间，求最少移除多少个区间，使得剩余区间互不重叠。

等价于求：最多能保留多少个互不重叠的区间（最大不相交区间数），然后用 总数量 - 保留数量 即为答案。

这是一个经典的贪心算法问题：

核心策略：按区间的右端点升序排序，每次选择右端点最小的区间，这样能为后面留下最多的空间。如果当前区间的左端点 ≥ 上一个选中区间的右端点，则说明不重叠，可以保留。

Java 实现

解法一：按右端点排序（推荐）

importjava.util.Arrays;classSolution{publicinteraseOverlapIntervals(int[][]intervals){if(intervals.length==0)return0;// 按区间右端点升序排序Arrays.sort(intervals,(a,b)->Integer.compare(a[1],b[1]));intkeep=1;// 至少保留第一个区间intend=intervals[0][1];// 上一个保留区间的右端点for(inti=1;i<intervals.length;i++){// 当前区间左端点 >= 上一个区间的右端点 → 不重叠，可以保留if(intervals[i][0]>=end){keep++;end=intervals[i][1];}// 否则重叠，该区间被移除（不计数）}returnintervals.length-keep;}}

解法二：直接统计移除数量

importjava.util.Arrays;classSolution{publicinteraseOverlapIntervals(int[][]intervals){// 按右端点升序Arrays.sort(intervals,(a,b)->Integer.compare(a[1],b[1]));intremoved=0;intend=Integer.MIN_VALUE;for(int[]interval:intervals){if(interval[0]>=end){// 不重叠，保留，更新右端点end=interval[1];}else{// 重叠，需要移除该区间removed++;}}returnremoved;}}

举例分析

输入：intervals = [[1,2],[2,3],[3,4],[1,3]]

按右端点排序后：[[1,2],[2,3],[1,3],[3,4]]

区间 左端点 当前 end 是否保留
[1,2] 1 MIN ✅ 保留，end=2
[2,3] 2 2 ✅ 保留（2 >= 2），end=3
[1,3] 1 3 ❌ 移除（1 < 3）
[3,4] 3 3 ✅ 保留（3 >= 3），end=4

结果：移除 1 个区间，返回 1。

为什么按右端点排序？

· 按右端点排序后，每次选中右端点最小的区间，能让「已选区间」的结束位置尽可能靠左，从而给后续区间留下最大空间，可以贪心地得到最优解。
· 如果按左端点排序，虽然也能解决（转换成找「不重叠」的最优解），但按右端点排序是最标准、最直观的贪心方式。

复杂度分析

· 时间复杂度：O(n log n)，主要开销在排序，遍历为 O(n)。
· 空间复杂度：O(log n)，为排序所需的栈空间（Java 中 Arrays.sort 对对象数组使用归并/TimSort）。

注意点

1. “重叠” 的判定：题目中 [1,2] 和 [2,3] 视为不重叠（端点相接不算重叠），所以判断条件是 interval[0] >= end 而不是 >。
2. 排序使用 Integer.compare 而非 a[1] - b[1]，避免极端值下发生整型溢出。
3. 该题与 LeetCode 452. 用最少数量的箭引爆气球 思路几乎一致，可以对照学习。