合并区间

题目

56. 合并区间 - 力扣（LeetCode）

解法

思路

问题分析：给定一组区间，需要合并所有重叠的区间。例如，[1,3] 和 [2,6] 重叠，应合并为 [1,6]。

核心思想：先按左边界排序，再遍历合并。排序后，重叠的区间必然相邻，这样只需一次遍历。

为什么排序？ 如果不排序，需要两两比较，时间复杂度 O(n^2)。排序后，只需比较相邻区间，总复杂度 O(n log n)。

合并条件：设当前区间为 cur = [a, b]，新区间为 [c, d]。如果 c ≤ b，则重叠，合并后的区间为 [a, max(b, d)]。否则不重叠，将 cur 加入结果。

边界情况：如果输入为空，直接返回空列表。

答案

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 按左边界排序
        intervals.sort(key=lambda x: x[0])
        
        res = []
        if not intervals:  # 空列表处理
            return res
        cur = intervals[0]
        for i in range(1, len(intervals)):
            if intervals[i][0] <= cur[1]:  # 重叠
                # 更新右边界为较大值
                cur[1] = max(cur[1], intervals[i][1])
            else:  # 不重叠
                res.append(cur)
                cur = intervals[i]
        # 加入最后一个区间
        res.append(cur)
        return res

代码说明：

• intervals.sort(key=lambda x: x[0])：按每个子列表的第一个元素（左边界）排序。
• cur 用于跟踪当前正在合并的区间。
• 遍历时，如果新区间与 cur 重叠，则合并；否则将 cur 存入结果，并开始新的合并。

收获

通过本题，学会了 Python 中多维列表的排序方法。下面详细说明：

Python 列表排序：

• list.sort(key=None, reverse=False)：原地排序。
• key 参数指定一个函数，用于从每个元素中提取比较键。
• 对于多维列表，常用 lambda x: x[0] 按第一个元素排序，lambda x: x[1] 按第二个元素排序。
• 示例：intervals = [[1,3],[2,6],[8,10]]，intervals.sort(key=lambda x: x[0]) 后得到 [[1,3],[2,6],[8,10]]。

扩展：类似题目还有 LeetCode 57. 插入区间、LeetCode 435. 无重叠区间，都用到区间排序和合并的思想。