LeetCode 435. 无重叠区间题目思路给定若干区间求最少移除多少个区间使得剩余区间互不重叠。等价于求最多能保留多少个互不重叠的区间最大不相交区间数然后用 总数量 - 保留数量 即为答案。这是一个经典的贪心算法问题核心策略按区间的右端点升序排序每次选择右端点最小的区间这样能为后面留下最多的空间。如果当前区间的左端点 ≥ 上一个选中区间的右端点则说明不重叠可以保留。Java 实现解法一按右端点排序推荐importjava.util.Arrays;classSolution{publicinteraseOverlapIntervals(int[][]intervals){if(intervals.length0)return0;// 按区间右端点升序排序Arrays.sort(intervals,(a,b)-Integer.compare(a[1],b[1]));intkeep1;// 至少保留第一个区间intendintervals[0][1];// 上一个保留区间的右端点for(inti1;iintervals.length;i){// 当前区间左端点 上一个区间的右端点 → 不重叠可以保留if(intervals[i][0]end){keep;endintervals[i][1];}// 否则重叠该区间被移除不计数}returnintervals.length-keep;}}解法二直接统计移除数量importjava.util.Arrays;classSolution{publicinteraseOverlapIntervals(int[][]intervals){// 按右端点升序Arrays.sort(intervals,(a,b)-Integer.compare(a[1],b[1]));intremoved0;intendInteger.MIN_VALUE;for(int[]interval:intervals){if(interval[0]end){// 不重叠保留更新右端点endinterval[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 ✅ 保留end2[2,3] 2 2 ✅ 保留2 2end3[1,3] 1 3 ❌ 移除1 3[3,4] 3 3 ✅ 保留3 3end4结果移除 1 个区间返回 1。为什么按右端点排序· 按右端点排序后每次选中右端点最小的区间能让「已选区间」的结束位置尽可能靠左从而给后续区间留下最大空间可以贪心地得到最优解。· 如果按左端点排序虽然也能解决转换成找「不重叠」的最优解但按右端点排序是最标准、最直观的贪心方式。复杂度分析· 时间复杂度O(n log n)主要开销在排序遍历为 O(n)。· 空间复杂度O(log n)为排序所需的栈空间Java 中 Arrays.sort 对对象数组使用归并/TimSort。注意点“重叠” 的判定题目中 [1,2] 和 [2,3] 视为不重叠端点相接不算重叠所以判断条件是 interval[0] end 而不是 。排序使用 Integer.compare 而非 a[1] - b[1]避免极端值下发生整型溢出。该题与 LeetCode 452. 用最少数量的箭引爆气球 思路几乎一致可以对照学习。
