56. 合并区间

Origin: LeetCode 56

题目描述

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

示例

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] Output: [[1, 6], [8, 10], [15, 18]] Explanation: [1, 3] 和 [2, 6] 重叠，合并为 [1, 6]

Input: intervals = [[1, 4], [4, 5]] Output: [[1, 5]] Explanation: [1, 4] 和 [4, 5] 重叠（端点接触算重叠）

约束

• 1 <= intervals.length <= 10
• intervals[i].length == 2
• 0 <= start <= end <= 10

关键信息

• 先按 start 排序
• 遍历，当前区间和结果最后一个区间比较
• 重叠 → 合并（取较大的 end）
• 不重叠 → push 到结果

Resolution

我的解法

function merge(intervals: number[][]): number[][] {
    if (!intervals.length) return []
 
    intervals.sort((a, b) => a[0] - b[0])
 
    let result: number[][] = []
 
    for (let i = 0; i < intervals.length; i++) {
        let [start, end] = intervals[i]
        let right = i + 1
        let tmpRes: number[] = [start, end]
        while (intervals[right] && end >= intervals[right][0] && right < intervals.length) {
            end = Math.max(intervals[right][1], end)
            tmpRes = [start, end]
            i = right
            right++
        }
        result.push(tmpRes)
    }
 
    return result
}

标准解法（更简洁）

function merge(intervals: number[][]): number[][] {
    if (!intervals.length) return []
 
    intervals.sort((a, b) => a[0] - b[0])
 
    const result: number[][] = [intervals[0]]
 
    for (let i = 1; i < intervals.length; i++) {
        const last = result[result.length - 1]
        if (intervals[i][0] <= last[1]) {
            // 重叠，合并 end
            last[1] = Math.max(last[1], intervals[i][1])
        } else {
            // 不重叠，push
            result.push(intervals[i])
        }
    }
 
    return result
}

解题思路

排序后遍历，和结果最后一个区间比较：

• 当前区间 start <= last 的 end → 重叠，合并（取较大的 end）
• 否则 → 不重叠，push 到结果

你的解法 vs 标准解法

你的写法用 while 内层循环批量合并 + i = right 跳过已合并的区间。标准解法只用 for + if，每次只和结果最后一个比。两种都正确，标准解法更简洁，不需要手动控制 i。

复杂度

• 时间：O(n log n)，排序
• 空间：O(n)，结果数组