无重叠区间

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

LeetCode 435. Non-overlapping Intervals

题目描述

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

注意：区间 [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
解释：本就互不重叠，无需移除。

约束：，。

思路拆解：从暴力到最优

换个角度看问题

「移除最少的区间使剩余不重叠」，等价于「保留最多的互不重叠区间」。设总数为 ，能保留的最多不重叠区间数为 ，那么答案就是 。

这一步转化很关键：把「删除问题」变成了经典的「最多不重叠区间选择」——也就是著名的活动安排问题。

想法一：动态规划（暴力思路）

先按起点排序，定义 dp[i] 为「以第 个区间结尾时，能保留的最多不重叠区间数」。对每个 ，回看前面所有与它不冲突的 ，取最大值：

点击展开暴力解法（DP）

function eraseOverlapIntervals(intervals) {
  if (intervals.length === 0) return 0;
  intervals.sort((a, b) => a[0] - b[0]); // 按起点排序
  const n = intervals.length;
  const dp = new Array(n).fill(1);       // 每个区间至少能自己保留
  let best = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      // 前一个区间的结束 <= 当前区间的开始，才不冲突
      if (intervals[j][1] <= intervals[i][0]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    best = Math.max(best, dp[i]);
  }
  return n - best; // 总数 - 最多保留数
}

• 时间：，双重循环。
• 空间：，DP 数组。

思路正确，但 时 会超时。

为什么要找更优解？

DP 把「最多保留」算对了，但它枚举所有配对，代价是平方级。这类「区间选择」问题其实有一个非常漂亮的贪心规律，能把复杂度降到排序的 。关键在于想清楚：每一步该优先保留哪个区间，才能给后面留出最多空间？

想法二：贪心 · 按右端点排序（最优解）

核心思路

按「结束时间」从小到大排序，每次贪心保留结束最早的区间。

直觉：一个区间结束得越早，它占用的时间越少，就能给后面留出越多空间去容纳更多区间。所以我们优先保留结束最早的那个。

具体做法：

1. 把所有区间按右端点 end 升序排序。
2. 用一个变量 end 记录「上一个保留区间的右端点」，初始为 。
3. 顺序扫描每个区间 [s, e]：
   • 若 s >= end，说明不重叠 → 保留它，更新 end = e；
   • 若 s < end，说明与上一个保留区间重叠 → 删除它，count++。
4. count 就是最少删除数。

为什么按右端点排序是对的？ 这是一个可以严格证明的贪心（交换论证）：在所有能选的区间里，选结束最早的那个一定不会让答案变差——因为它「让位」最多，任何其他选择都不会比它更优。这正是活动安排问题的经典结论。

动态演示

下面的动画完整演示了对 [[1,2],[2,3],[3,4],[1,3]] 的贪心全过程——先按右端点排序，再从左到右扫描、逐个决定「保留」还是「删除」：

步骤 1 / 7初始区间

正在处理保留删除已删除：0

[1, 2]

[2, 3]

[3, 4]

[1, 3]

012345

初始区间（原始顺序）：[1,2]、[2,3]、[3,4]、[1,3]。目标：删最少，使剩余不重叠。

完整代码（JavaScript）

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function eraseOverlapIntervals(intervals) {
  if (intervals.length <= 1) return 0;

  // 1) 按右端点 end 升序排序
  intervals.sort((a, b) => a[1] - b[1]);

  let count = 0;               // 删除计数
  let end = intervals[0][1];   // 第一个区间必被保留，记下它的右端点

  // 2) 从第 2 个区间开始扫描
  for (let i = 1; i < intervals.length; i++) {
    const [s, e] = intervals[i];
    if (s >= end) {
      end = e;                 // 不重叠：保留，更新右边界
    } else {
      count++;                 // 重叠：删除当前区间（end 保持不变）
    }
  }
  return count;
}

另一种等价写法：按左端点排序

也可以按左端点排序，重叠时贪心地「删掉右端点更大的那个」（保留右端点小的）：

function eraseOverlapIntervals(intervals) {
  if (intervals.length <= 1) return 0;
  intervals.sort((a, b) => a[0] - b[0]); // 按起点排序
  let count = 0;
  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    const [s, e] = intervals[i];
    if (s < end) {              // 重叠
      count++;
      end = Math.min(end, e);   // 关键：保留右端点更小的，留更多空间
    } else {
      end = e;                  // 不重叠，更新
    }
  }
  return count;
}

两种写法本质相同，但按右端点排序更直观、更不易错，推荐首选。

复杂度分析

设区间数量为 。

解法	时间复杂度	空间复杂度	说明
动态规划			枚举所有配对， 大会超时
贪心（按右端点排序）			排序主导，扫描 ，最优

为什么贪心是 ？ 排序需要 ，之后只需一次线性扫描 ，总体由排序主导。除了排序本身，只用了 count、end 两个变量，额外空间 。

边界与易错点

易错点

1. 排序键选右端点，不是左端点。贪心正确性依赖「优先保留结束最早的区间」，所以要 sort((a, b) => a[1] - b[1])。按左端点排序需要配合「删右端点更大者」的额外逻辑，写错就得不到最优解。

2. 边界接触不算重叠。[1,2] 和 [2,3] 不冲突，所以判定条件用 s >= end（含等号）表示「可保留」。若误写成 s > end，会把接触的区间也误删。

3. 删除时不要更新 end。当区间被删除（重叠）时，end 必须保持不变——因为被保留的仍是之前那个结束更早的区间。初学者常犯「删了还顺手更新 end」的错。

4. 空数组 / 单区间。intervals 为空或只有一个区间时，答案为 0。开头 if (intervals.length <= 1) return 0; 已覆盖。

5. 返回的是删除数，不是保留数。题目要「最少移除数量」。贪心里的 count 直接就是删除数；若用 DP 求的是最多保留数 best，记得返回 n - best。

6. 排序会修改原数组。sort 是原地排序，若调用方还需要原始顺序，应先拷贝一份再排。

简易解题思路（记忆口诀）

「按右端排个序，结束早的先留住；下家开始不早于它，就留；否则算重叠，删一步。」

拆开记：

口诀	对应操作
按右端排序	sort((a,b) => a[1] - b[1])
结束早的先留住	第一个区间必保留，记下其 end
开始不早于它就留	s >= end → 保留，更新 end = e
否则重叠删一步	s < end → count++，end 不动

一句话记住本质：贪心保留「结束最早」的区间——它占地最少、留白最多，能塞下最多的后续区间；剩下和它撞车的，就是要删的数量。