算法 - 合并区间 (Merge Intervals)

Posted on

1. 题目

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

示例:

1
2
3
4
5
6
7
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: [1,3] 与 [2,6] 重叠，合并为 [1,6]

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 端点相接也算重叠

2. 解题思路

区间能否合并，取决于它们在数轴上的相对位置。若无序，两个区间可能隔着十万八千里却要判重，非常麻烦。核心思路：先按左端点排序，让可能重叠的区间彼此相邻，然后一次线性扫描。

排序后遍历，维护结果数组 res，对当前区间 cur：

  1. 若 res 为空，或 cur.start > res 最后一个.end（不重叠）→ 直接 push 新区间。
  2. 否则说明重叠 → 合并：更新最后一个区间的 end = max(旧end, cur.end)。

为什么是 max？考虑 [[1,10],[2,3]]，第二个区间完全被包含，end 不能取 cur.end，要保留较大的那个。

  • 时间复杂度：O(n log n)，排序主导。
  • 空间复杂度：O(n)（存结果；不计则为 O(log n) 排序栈）。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function merge(intervals: number[][]): number[][] {
    if (intervals.length === 0) return [];

    // 按左端点升序
    intervals.sort((a, b) => a[0] - b[0]);

    const res: number[][] = [];

    for (const cur of intervals) {
        const last = res[res.length - 1];

        // 无结果 或 与上一个不重叠 -> 开新区间
        if (!last || cur[0] > last[1]) {
            res.push([...cur]);
        } else {
            // 重叠 -> 合并，取右端点较大者
            last[1] = Math.max(last[1], cur[1]);
        }
    }

    return res;
}

// 测试
console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]));
// [[1,6],[8,10],[15,18]]
console.log(merge([[1, 4], [4, 5]])); // [[1,5]]
console.log(merge([[1, 10], [2, 3]])); // [[1,10]]

4. 面试延伸

  • 插入区间（57 题）：找到插入位置，把与新区间相交的全部吞并，取新端点。
  • 区间相交 / 无重叠最少删除（435 题）：按右端点排序 + 贪心，是另一条主线，别和本题的左端点排序搞混。
  • 会议室 II（253 题）：求同时进行的最多区间数，用最小堆或「起点/终点分别排序 + 双指针扫描线」。
  • 通用套路：区间题先想排序策略（按左？按右？），再决定扫描时维护什么状态。

难度：中等 | LeetCode 56 题 | 排序 + 扫描线经典