好的，我们来看 LeetCode 第 56 题「合并区间」。

1. 题目描述

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

示例 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. 题意理解

• 区间 [a, b] 和 [c, d] 重叠的条件是：c <= b（即第二个区间的开始 ≤ 第一个区间的结束）。
• 如果重叠，合并后的区间是 [a, max(b, d)]。
• 最终结果中各个区间应互不重叠，且覆盖所有原区间。

3. 思路分析

关键直觉

如果我们将区间按照起点从小到大排序，那么需要合并的区间一定是连续的。
因为如果区间 i 和 i+1 不重叠，那么区间 i 更不可能和 i+2 重叠（因为 i+2 的起点 ≥ i+1 的起点 > i 的终点）。

步骤

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

4. 详细例子演示

输入：[[1,3],[2,6],[8,10],[15,18]]

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

初始化 merged = [[1,3]]

• 遍历 [2,6]：

  • 比较 2 <= 3（重叠）
  • 更新最后一个区间终点为 max(3, 6) = 6
  • merged = [[1,6]]

• 遍历 [8,10]：

  • 8 <= 6？否，不重叠
  • 加入 [8,10]，merged = [[1,6],[8,10]]

• 遍历 [15,18]：

  • 15 <= 10？否，不重叠
  • 加入 [15,18]，merged = [[1,6],[8,10],[15,18]]

输出：[[1,6],[8,10],[15,18]]

5. 边界情况考虑

• 空输入：[] → 返回 []
• 单个区间：[[1,2]] → 返回 [[1,2]]
• 完全包含的区间：[[1,4],[2,3]] → 合并为 [[1,4]]
• 多个区间需要连续合并：[[1,4],[2,5],[5,8]] → 合并为 [[1,8]]

6. 代码实现（Python）

def merge(intervals):
    if not intervals:
        return []
    
    # 按区间起点排序
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    for interval in intervals:
        # 如果 merged 为空，或当前区间与最后一个区间不重叠，直接添加
        if not merged or interval[0] > merged[-1][1]:
            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)（存储结果）

这样，我们就完成了「合并区间」的题目讲解，从理解题意到排序合并的思路，再到代码实现和复杂度分析，每一步都力求清晰。