合并区间

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：数组、排序

以数组 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] 可被视为重叠区间。

2. 解题思路拆解

方法：排序 + 一次遍历

要合并区间，首先我们需要让这些区间有序。如果区间是乱序的，我们很难判断谁和谁重叠。

排序：
- 按照区间的左端点（start）进行升序排序。
- 排序后，重叠的区间一定是相邻的（或者相近的）。
遍历合并：
- 创建一个 merged 数组用于存储最终结果。
- 首先将第一个区间加入 merged。
- 然后从第二个区间开始遍历：
  - 取出 merged 中最后一个区间，记为 last。
  - 取出当前遍历到的区间，记为 curr。
  - 判断重叠：如果 curr 的左端点 <= last 的右端点（curr.start <= last.end），说明两个区间重叠。
    - 合并操作：更新 last 的右端点为两个区间右端点的最大值（last.end = max(last.end, curr.end)）。注意左端点不需要动，因为已经排过序了，last 的左端点一定更小。
  - 不重叠：如果 curr 的左端点 > last 的右端点，说明出现了断层。
    - 直接将 curr 加入 merged 数组。

3. 代码实现

javascript

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    if (intervals.length === 0) return [];
    
    // 1. 按照左端点升序排序
    intervals.sort((a, b) => a[0] - b[0]);
    
    const merged = [];
    merged.push(intervals[0]);
    
    for (let i = 1; i < intervals.length; i++) {
        const curr = intervals[i];
        const last = merged[merged.length - 1];
        
        // 2. 判断是否有重叠
        if (curr[0] <= last[1]) {
            // 有重叠，合并：更新右端点为两者的最大值
            last[1] = Math.max(last[1], curr[1]);
        } else {
            // 无重叠，直接加入结果集
            merged.push(curr);
        }
    }
    
    return merged;
};

代码执行演示

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

排序：[[1,3],[2,6],[8,10],[15,18]] (已经是排好序的)
初始化：merged = [[1,3]]
遍历 i=1 ([2,6])：
- last = [1,3]
- curr[0] (2) <= last[1] (3) -> 重叠
- 更新 last[1] = max(3, 6) = 6
- merged = [[1,6]]
遍历 i=2 ([8,10])：
- last = [1,6]
- curr[0] (8) > last[1] (6) -> 不重叠
- 加入 merged
- merged = [[1,6], [8,10]]
遍历 i=3 ([15,18])：
- last = [8,10]
- curr[0] (15) > last[1] (10) -> 不重叠
- 加入 merged
- merged = [[1,6], [8,10], [15,18]]

最终返回 [[1,6], [8,10], [15,18]]。

4. 复杂度分析

维度	描述
时间复杂度	$O(n \log n)$。主要开销在于排序，排序通常需要 $O(n \log n)$ 的时间。遍历只需要 $O(n)$。
空间复杂度	$O(\log n)$。排序所需要的栈空间（如果不算输出数组占用空间）。

合并区间 ​

1. 题目呈现 ​

2. 解题思路拆解 ​

方法：排序 + 一次遍历 ​

3. 代码实现 ​

代码执行演示 ​