合并区间

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

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2：

输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

简单做法：先用starti排序，再从第二个开始遍历，和前一个区间比较有没有重叠（前endi >= 后starti 为重叠），重叠则将两个数组合并成[前starti, 后endi（取两个endi的大值）],继续往后遍历（和进阶做法一致）

进阶做法：要合并所有重叠的区间，关键在于对区间进行排序后，通过一次遍历合并相邻且重叠的区间。以下是具体的方法和实现：

方法思路

排序区间：按区间的起始点（start）对所有区间进行升序排序。若起始点相同，则按结束点（end）排序。
初始化结果列表：将第一个区间加入结果列表。
遍历合并：从第二个区间开始，依次检查当前区间是否与结果列表中最后一个区间重叠：
- 若重叠，则合并两个区间（更新结果列表中最后一个区间的结束点为两者的最大值）。
- 若不重叠，则将当前区间直接加入结果列表。

代码实现

function merge(intervals) {
    if (intervals.length <= 1) return intervals;
    
    // 按区间起始点升序排序
    intervals.sort((a, b) => a[0] - b[0]);
    
    const result = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const current = intervals[i];
        const last = result[result.length - 1];
        
        // 检查是否重叠（当前区间的start <= 结果中最后区间的end）
        if (current[0] <= last[1]) {
            // 合并区间：更新结果中最后区间的end为较大值
            last[1] = Math.max(last[1], current[1]);
        } else {
            // 不重叠，直接添加当前区间
            result.push(current);
        }
    }
    
    return result;
}

代码解释

排序：使用 sort 方法按区间起始点排序，确保相邻区间的起始点递增。
初始化结果：将排序后的第一个区间加入结果列表，作为初始参考。
遍历合并：
- 若当前区间的起始点 ≤ 结果列表中最后区间的结束点，则合并（更新结束点）。
- 否则，将当前区间添加到结果列表。

复杂度分析

时间复杂度：O(n log n)，主要来自排序操作。遍历区间的时间为 O(n)，整体复杂度由排序主导。
空间复杂度：O(log n)（排序所需的栈空间）或 O(n)（存储结果），取决于具体实现。

示例分析

输入 intervals = [[1,3],[2,6],[8,10],[15,18]]：

排序后：[[1,3],[2,6],[8,10],[15,18]]（已排序）。
遍历合并：
- 初始结果：[[1,3]]。
- 处理 [2,6]：2 ≤ 3，合并为 [1,6]，结果变为 [[1,6]]。
- 处理 [8,10]：8 > 6，不重叠，添加 [8,10]，结果变为 [[1,6],[8,10]]。
- 处理 [15,18]：15 > 10，不重叠，添加 [15,18]，结果变为 [[1,6],[8,10],[15,18]]。

最终输出：[[1,6],[8,10],[15,18]]。

其他解法对比

暴力法：枚举所有区间对，检查重叠并合并。时间复杂度 O(n²)，效率低。
扫描线算法：将区间拆分为起点和终点的事件点，按时间排序后扫描。适用于更复杂的区间问题，但本题使用排序合并更简洁。

排序合并法是解决区间合并问题的最优解，通过一次遍历和排序操作高效完成合并。

方法思路​

代码实现​

代码解释​

复杂度分析​

示例分析​

其他解法对比​