56. 合并区间

题目链接（中等）

题目描述

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

数据范围：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

示例

示例 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] 可被视为重叠区间。

示例 3：

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

方法一：排序 + 线性扫描

思路及解法

按区间的左端点升序排序。排完序后，可以合并的区间一定是连续的，从左到右一次扫描即可完成合并。

具体做法：

1. 对 intervals 按左端点升序排序；
2. 用 merged 存结果，从左往右遍历：
   • 若 merged 为空，或当前区间的左端点 > merged 最后一个区间的右端点（不重叠），直接把当前区间加入 merged；
   • 否则它们重叠，用当前区间的右端点更新 merged[-1][1] = max(merged[-1][1], interval[1])。

排序后，区间要么和前面重叠，要么完全在后面。只需要动态维护“当前合并中的区间的右端点”，遇到不重叠的就开一段新的。

代码

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

复杂度分析

• 时间复杂度：$O(n \log n)$，主要开销是排序，之后的线性扫描为 $O(n)$。
• 空间复杂度：$O(\log n)$，除答案数组外，排序所需的额外空间为 $O(\log n)$。

总结

• 核心操作：按左端点排序 + 一次线性扫描；
• 判断重叠：merged[-1][1] >= interval[0] 即为重叠，合并时取右侧最大值；
• 关键结论：排序后可以合并的区间一定是连续的，因此一次扫描足够；
• 时间复杂度 $O(n \log n)$，空间复杂度 $O(\log n)$。