我随机选择 LeetCode 第 56 题「合并区间」，这道题考察数组操作与贪心思想，适合循序渐进理解。

1. 题目描述

题目：
给出一个区间的集合，请合并所有重叠的区间。

示例 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，表示区间起点和终点。

2. 题意理解

• 区间用 [start, end] 表示。
• 如果两个区间有重叠（包括端点相接如 [1,4] 和 [4,5]），就合并成一个区间。
• 合并后的区间应覆盖原来两个区间的范围。
• 最终输出不重叠的区间列表，且按区间起点升序排列。

重叠的定义：
区间 A = [a1, a2]，区间 B = [b1, b2]（假设 a1 ≤ b1），如果 a2 >= b1，则它们重叠，合并后为 [a1, max(a2, b2)]。

3. 思路分析

关键直觉

如果区间按起点排序，那么需要合并的区间一定是连续的。
因为如果 [a1, a2] 和 [b1, b2] 重叠（a1 ≤ b1），但 a2 ≥ b1，那么 [a1, a2] 与 b1 之后的区间也可能重叠，但 b1 之前的区间不会与 b1 之后的区间重叠（因为起点已排序）。

步骤：

1. 按区间起点排序。
2. 初始化结果列表，放入第一个区间。
3. 遍历后续每个区间：
   • 如果当前区间与结果列表中最后一个区间重叠，则更新最后一个区间的终点（取最大值）。
   • 如果不重叠，则把当前区间加入结果列表。

4. 详细步骤演示

以 intervals = [[1,3],[2,6],[8,10],[15,18]] 为例：

排序后（本身已按起点有序）：
[1,3], [2,6], [8,10], [15,18]

1. 结果列表 merged = []
2. 放入第一个区间 [1,3] → merged = [[1,3]]
3. 遍历到 [2,6]：
   • 比较 [1,3] 与 [2,6]：3 >= 2 → 重叠
   • 合并：[1, max(3,6)] = [1,6]
   • 更新 merged 最后一个区间：[[1,6]]
4. 遍历到 [8,10]：
   • 比较 [1,6] 与 [8,10]：6 < 8 → 不重叠
   • 加入 merged：[[1,6], [8,10]]
5. 遍历到 [15,18]：
   • 比较 [8,10] 与 [15,18]：10 < 15 → 不重叠
   • 加入 merged：[[1,6], [8,10], [15,18]]
6. 结束。

5. 边界情况考虑

• 空输入：返回空列表。
• 单个区间：直接返回该区间。
• 完全包含的区间：如 [1,4] 和 [2,3]，合并后应为 [1,4]（取 max 终点即可处理）。
• 多个区间需要连续合并：如 [1,5], [2,4], [3,6] → 排序后一步步合并：
  • [1,5] 与 [2,4] 合并为 [1,5]
  • [1,5] 与 [3,6] 合并为 [1,6]

6. 代码实现（Python）

def merge(intervals):
    if not intervals:
        return []
    
    # 按区间起点排序
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    for interval in intervals:
        # 如果 merged 为空，或当前区间与 merged 最后一个区间不重叠
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # 重叠，合并
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged

7. 复杂度分析

• 排序：O(n log n)
• 一次遍历：O(n)
• 总时间复杂度：O(n log n)
• 空间复杂度：O(log n) 或 O(n)（取决于排序的额外空间，Python 的 Timsort 需要 O(n) 最坏情况？其实 Timsort 最坏 O(n log n) 空间，但平均 O(log n)，这里通常说 O(n) 或 O(log n) 都可以，但更准确是 O(log n) 或 O(n) 看语言实现。Python 中 sort() 空间复杂度最坏 O(n)，平均 O(log n)。）

8. 总结

• 核心思想：排序后贪心合并。
• 关键点：判断重叠的条件是 last_end >= current_start。
• 适用场景：所有需要合并重叠区间的问题都可套用此模板。

希望这个逐步拆解让你清晰理解了合并区间的解法！