008-合并区间（排序+合并）

合并区间

问题描述

给定一个区间集合 intervals，其中 intervals[i] = [starti, endi]，合并所有重叠的区间，并返回一个不重叠的区间数组。

示例

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠，合并为 [1,6]

解决思路

方法：排序 + 合并

1. 排序：首先将所有区间按照起始点进行排序
2. 合并：然后遍历排序后的区间，逐个合并重叠的区间

算法步骤

1. 如果区间数量为0，直接返回空数组
2. 按区间的起始点进行排序
3. 初始化结果数组，放入第一个区间
4. 从第二个区间开始遍历：
   • 如果当前区间的起始点 <= 结果数组中最后一个区间的结束点（有重叠）
     • 合并这两个区间，更新结果数组最后一个区间的结束点为两者的较大值
   • 否则（无重叠）
     • 直接将当前区间加入结果数组

JavaScript实现

function merge(intervals) {
    if (intervals.length === 0) return [];
    
    // 按起始点排序
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [intervals[0]];
    
    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        const current = intervals[i];
        
        if (current[0] <= last[1]) {
            // 有重叠，合并区间
            last[1] = Math.max(last[1], current[1]);
        } else {
            // 无重叠，直接添加
            merged.push(current);
        }
    }
    
    return merged;
}

示例解析

以输入 [[1,3],[2,6],[8,10],[15,18]] 为例：

1. 排序后（已有序）：[[1,3],[2,6],[8,10],[15,18]]
2. 初始化：merged = [[1,3]]
3. **处理 [2,6]**：
   • 比较 2 <= 3 → 有重叠
   • 合并为 [1, max(3,6)] = [1,6]
   • merged = [[1,6]]
4. **处理 [8,10]**：
   • 比较 8 <= 6 → 无重叠
   • 直接添加
   • merged = [[1,6],[8,10]]
5. **处理 [15,18]**：
   • 比较 15 <= 10 → 无重叠
   • 直接添加
   • merged = [[1,6],[8,10],[15,18]]
6. 最终结果：[[1,6],[8,10],[15,18]]

复杂度分析

• 时间复杂度：O(n log n)，主要来自排序操作
• 空间复杂度：O(n)，存储结果需要额外空间

边界情况考虑

1. 空输入：直接返回空数组
2. 单区间输入：直接返回原数组
3. 完全重叠区间：如 [[1,4],[2,3]] 应合并为 [[1,4]]
4. 相邻区间：如 [[1,4],[4,5]] 应合并为 [[1,5]]

可视化示例

原始区间：
[1,3] [2,6] [8,10] [15,18]
  |----|
    |------|
           |----|
                 |-----|

合并过程：
1. [1,3] 和 [2,6] 重叠 → [1,6]
2. [1,6] 和 [8,10] 不重叠
3. [8,10] 和 [15,18] 不重叠

最终结果：
[1,6] [8,10] [15,18]
 |------|
         |----|
               |-----|

总结

合并区间问题的关键在于：

1. 先排序使区间有序
2. 逐个比较并合并重叠区间
3. 注意处理各种边界情况

这种方法高效且易于理解，适用于大多数区间合并场景。