56. 合并区间

题目链接：56. 合并区间

题目描述

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

核心思考：如何判断区间重叠？

面对这道题，最直观的想法是我们怎么才能知道两个区间是否重叠？
如果数组是无序的，任何一个区间都可能和数组中的其他任意区间重叠，这就得需要 $O(n^2)$ 的暴力判断。

因此，先排序是解决区间问题的首要思路。
如果我们按照区间的**左端点（起点）**从小到大进行排序，那么所有区间就有了从左到右的确定顺序。

排好序后，对于遍历到的当前区间 curr = [curr_start, curr_end]，以及我们已经处理好的上一个区间（结果集中的最后一个区间 last = [last_start, last_end]），我们天然地满足了 last_start <= curr_start（前面的起点一定小于等于后面的起点）。

此时，判断两个区间是否重叠的条件就变得非常简单：

• 不重叠：如果 last_end < curr_start，说明前面区间的右端点还够不到当前区间的左端点，两者没有交集。我们可以放心把 curr 作为独立的区间加入结果集。
• 重叠：如果 last_end >= curr_start，说明两个区间有重叠，我们需要将它们合并。

合并的细节（包裹情况）：
合并区间时，左端点肯定是 last_start，那右端点应该怎么取呢？
不能简单地取 curr_end，因为在排序后，虽然 curr_start 大于等于前面的，但是 curr_end 完全有可能比较短（比如 [1, 5] 就在 [2, 3] 前面，[2, 3] 完全被包裹在里面）。所以，合并后的右端点应当取 max(last_end, curr_end)。

解题思路 (Python)

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 1. 按照区间的左端点进行升序排序
        intervals.sort(key=lambda x: x[0])
        
        merged = []
        
        # 2. 遍历每一个区间
        for curr in intervals:
            # 如果结果集为空，或者当前区间的左端点大于最后合并的右端点（无交集）
            if not merged or merged[-1][1] < curr[0]:
                merged.append(curr)
            # 有重叠，合并区间
            else:
                # 更新最后合并区间的右端点，取两者的最大值
                merged[-1][1] = max(merged[-1][1], curr[1])
                
        return merged

复杂度分析

• 时间复杂度：$O(n \log n)$，其中 $n$ 是区间的数量。对数组进行排序的时间复杂度为 $O(n \log n)$，随后线性的遍历数组只需要 $O(n)$。总计时间复杂度为 $O(n \log n)$。
• 空间复杂度：$O(\log n)$。排序通常需要 $O(\log n)$ 的栈空间。如果不将结果数组 merged 计入额外空间开销的话，仅有排序本身的常数级开销。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

import sys

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    # 1. 按照区间的左端点进行升序排序
    intervals.sort(key=lambda x: x[0])

    merged = []

    # 2. 遍历每一个区间
    for curr in intervals:
        # 如果结果集为空，或者当前区间的左端点大于最后合并的右端点（无交集）
        if not merged or merged[-1][1] < curr[0]:
            merged.append(curr)
        # 有重叠，合并区间
        else:
            # 更新最后合并区间的右端点，取两者的最大值
            merged[-1][1] = max(merged[-1][1], curr[1])

    return merged

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.merge(matrix)
    for v in result:\n        print(v, end=' ')\n    print()

if __name__ == "__main__":
    main()

运行示例：

echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py