跳到主要内容

合并区间

问题​

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i]。请你合并所有重叠的区间，并返回一个不重叠的区间数组。

示例：

输入：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] 可被视为重叠区间

来源：LeetCode 56. 合并区间

答案​

方法一：排序 + 一次遍历（推荐）​

核心思路：

  1. 按区间起点排序
  2. 依次遍历，如果当前区间与上一个重叠（当前起点 ≤ 上一个终点），就合并；否则加入新区间
mergeIntervals.ts
function merge(intervals: number[][]): number[][] {
  if (intervals.length <= 1) return intervals;

  // 按起点排序
  intervals.sort((a, b) => a[0] - b[0]);

  const result: number[][] = [intervals[0]];

  for (let i = 1; i < intervals.length; i++) {
    const last = result[result.length - 1]; // 结果数组中最后一个区间
    const curr = intervals[i];

    if (curr[0] <= last[1]) {
      // 有重叠，合并（取较大的终点）
      last[1] = Math.max(last[1], curr[1]);
    } else {
      // 无重叠，加入新区间
      result.push(curr);
    }
  }

  return result;
}

图解过程：

排序后：[[1,3], [2,6], [8,10], [15,18]]

Step 1: result = [[1,3]]

Step 2: [2,6] → 2 <= 3 (重叠) → 合并为 [1, max(3,6)] = [1,6]
  result = [[1,6]]

Step 3: [8,10] → 8 > 6 (不重叠) → 新增
  result = [[1,6], [8,10]]

Step 4: [15,18] → 15 > 10 (不重叠) → 新增
  result = [[1,6], [8,10], [15,18]]
复杂度分析
  • 时间复杂度：O(nlog⁡n)O(n \log n) — 排序
  • 空间复杂度：O(log⁡n)O(\log n) — 排序的栈空间（不算输出）
容易出错的点
  1. 忘记排序：不排序的话无法保证左边的区间先处理
  2. 合并时只更新 end：last[1] = Math.max(last[1], curr[1])，不能直接 last[1] = curr[1]，因为可能 curr 被完全包含在 last 中
  3. 排序比较函数：JS/TS 的 sort() 默认按字符串排序，必须传比较函数

方法二：使用 reduce​

函数式写法：

mergeIntervalsReduce.ts
function merge(intervals: number[][]): number[][] {
  return intervals
    .sort((a, b) => a[0] - b[0])
    .reduce<number[][]>((result, curr) => {
      const last = result[result.length - 1];

      if (result.length > 0 && curr[0] <= last[1]) {
        last[1] = Math.max(last[1], curr[1]);
      } else {
        result.push([...curr]);
      }

      return result;
    }, []);
}

方法三：图/连通分量（了解即可）​

将每个区间看作图中的节点，有重叠的区间之间连边，每个连通分量合并为一个区间：

mergeIntervalsGraph.ts
function merge(intervals: number[][]): number[][] {
  const n = intervals.length;
  if (n <= 1) return intervals;

  // 构建邻接表（判断哪些区间重叠）
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (intervals[i][0] <= intervals[j][1] &&
          intervals[j][0] <= intervals[i][1]) {
        graph.get(i)!.push(j);
        graph.get(j)!.push(i);
      }
    }
  }

  // BFS 找连通分量
  const visited = new Set<number>();
  const result: number[][] = [];

  for (let i = 0; i < n; i++) {
    if (visited.has(i)) continue;

    const queue = [i];
    visited.add(i);
    let minStart = intervals[i][0];
    let maxEnd = intervals[i][1];

    while (queue.length > 0) {
      const node = queue.shift()!;
      for (const neighbor of graph.get(node)!) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
          minStart = Math.min(minStart, intervals[neighbor][0]);
          maxEnd = Math.max(maxEnd, intervals[neighbor][1]);
        }
      }
    }

    result.push([minStart, maxEnd]);
  }

  return result;
}
不推荐
  • 时间复杂度：O(n2)O(n^2) — 构建图
  • 远不如排序方法优秀，仅作为理解"区间重叠本质是连通性问题"的思维拓展

常见面试追问​

Q1: 如何插入一个新区间并保持不重叠？(LeetCode 57)​

答案：

function insert(
  intervals: number[][],
  newInterval: number[]
): number[][] {
  const result: number[][] = [];
  let i = 0;
  const n = intervals.length;

  // 添加所有在 newInterval 之前的区间
  while (i < n && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // 合并所有重叠的区间
  while (i < n && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
  }
  result.push(newInterval);

  // 添加剩余区间
  while (i < n) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

Q2: 如何判断两个区间是否重叠？​

答案：两个区间 [a, b] 和 [c, d] 重叠的条件为 a <= d && c <= b。

反过来理解更简单——不重叠的条件是 b < c || d < a（一个完全在另一个左边），取反就是重叠条件。

Q3: 如果区间是开区间/闭区间混合呢？​

答案：需要额外标记区间的开闭性质，在比较时考虑。例如 (1, 3) 和 [3, 5] 不重叠（因为端点 3 一个开一个闭），但 [1, 3] 和 [3, 5] 重叠。实际工程中常见于日期区间处理。

Q4: 区间调度问题——最多能参加几个不重叠的活动？​

答案：经典贪心问题。按结束时间排序，每次选结束最早的：

function maxNonOverlapping(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]); // 按结束时间排序
  let count = 0;
  let end = -Infinity;

  for (const [start, finish] of intervals) {
    if (start >= end) {
      count++;
      end = finish;
    }
  }

  return count;
}

相关链接​