好的，我们这次来看 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] 可被视为重叠区间。

注意：输入类型通常是 vector<vector<int>>（C++）或 List<int[]>（Java）等，每个内层数组长度为 2，表示区间起点和终点。

2. 题意理解

我们有一些区间，比如 [a, b] 表示从 a 到 b 的连续区间。
如果两个区间有重叠（一个区间的起点 <= 另一个区间的终点，并且有交集或刚好相接），就把它们合并成一个新区间，新区间的起点是两者中更小的起点，终点是两者中更大的终点。

目标：扫描所有区间，合并所有能合并的，最后返回不重叠的区间列表。

3. 思路分析

关键点

合并的前提是区间有重叠，而区间在数轴上是无序给出的，如果顺序混乱，判断合并会不方便。

核心思想：

1. 先按每个区间的起点排序，这样相邻的区间在位置上更有可能重叠。
2. 依次遍历区间，判断当前区间和“已合并的最后一个区间”是否有重叠，有则合并，无则加入结果集。

4. 算法步骤

1. 排序：用每个区间的第一个元素（start）升序排序。
2. 初始化结果列表：把第一个区间加入结果列表。
3. 遍历区间（从第二个区间开始）：
   • 取出结果列表中的最后一个区间（当前已合并的最新区间）。
   • 比较当前遍历到的区间 current 的起点和最后一个区间的终点：
     • 如果 current[0] <= 最后一个区间的终点，说明有重叠，更新最后一个区间的终点为 max(最后一个区间的终点, current[1])。
     • 否则，无重叠，把 current 加入结果列表。
4. 返回结果列表。

5. 举例说明

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

排序（已经按 start 排序了）：不变。

过程：

• 结果列表 result = []
• 加入 [1,3] → result = [[1,3]]
• 看 [2,6]：最后一个区间是 [1,3]，2 <= 3 → 重叠，合并：[1, max(3,6)] = [1,6] → result = [[1,6]]
• 看 [8,10]：8 > 6 → 不重叠，加入 → result = [[1,6],[8,10]]
• 看 [15,18]：15 > 10 → 不重叠，加入 → result = [[1,6],[8,10],[15,18]]

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

6. 代码实现（C++ 风格伪代码）

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    
    // 按区间起点排序
    sort(intervals.begin(), intervals.end());
    
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);
    
    for (int i = 1; i < intervals.size(); i++) {
        // 当前区间
        vector<int>& current = intervals[i];
        // 已合并的最后一个区间
        vector<int>& last = merged.back();
        
        if (current[0] <= last[1]) {
            // 重叠，合并
            last[1] = max(last[1], current[1]);
        } else {
            // 不重叠，直接加入
            merged.push_back(current);
        }
    }
    
    return merged;
}

7. 复杂度分析

• 时间复杂度：O(n log n)，主要是排序开销，之后一次线性扫描 O(n)。
• 空间复杂度：O(log n) 或 O(n)，取决于排序的栈空间（快速排序递归栈 O(log n)），结果列表 O(n) 不算额外空间的话，额外空间是 O(log n)。

8. 边界情况考虑

• 空输入：直接返回空列表。
• 单个区间：无需合并，直接返回它。
• 完全分离的区间：如 [1,2], [3,4]，不合并。
• 一个大区间包含多个小区间：如 [1,10], [2,3], [4,5]，合并成 [1,10]。
• 区间端点相等算重叠：[1,4], [4,5] 合并成 [1,5]。

这样一步步分析，你应该能清晰地理解合并区间的思路和实现了。需要我进一步解释某一步吗？