合并区间 - Stellar Observer Protocol

631 字

3 分钟

合并区间

2025-08-18

Algorithms

数组

/

排序

题目描述#

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

解题思路#

区间排序：
- 按区间起始点升序排序
- 确保重叠区间相邻
顺序合并：
- 初始化结果数组，添加首个区间
- 遍历后续区间，判断是否与末位区间重叠
重叠判定：
- 当前区间起始 ≤ 末位区间结束 → 重叠
- 更新末位区间结束为两者最大值
非重叠处理：
- 直接将新区间加入结果
边界处理：
- 空输入直接返回
- 单区间无需合并

关键洞察#

排序必要性：
- 无序区间无法保证相邻扫描覆盖所有重叠
- 起始点排序使重叠区间连续分布
贪心策略：
- 每次只关注与最近结果区间的重叠
- 避免复杂回溯机制
端点处理：
- 区间[1,3]和[3,5]视为重叠
- 需合并为[1,5]
空间优化：
- 原地修改结果数组
- 避免额外存储

复杂度分析#

指标	说明
时间复杂度	O(n log n)：排序主导，合并扫描O(n)
空间复杂度	O(1) 或 O(n)：排序栈空间O(log n)，结果O(n)

代码实现#

1
/**
2
 * @param {number[][]} intervals
3
 * @return {number[][]}
4
 */
5
var merge = function (intervals) {
6
    intervals = intervals.sort((a, b) => a[0] - b[0]);
7
    const merged = [];
8
    for (let i = 0; i < intervals.length; i++) {
9
        const [l, r] = intervals[i];
10
        if (merged.length === 0 || merged[merged.length - 1][1] < l) {
11
            merged.push([l, r])
12
        } else {
13
            merged[merged.length - 1][1] = Math.max(
14
                merged[merged.length - 1][1],
15
                r
16
            )
17
        }
18
    }
19
    return merged;
20
};