1. 这题为什么要先排序#

题目给的是一堆区间：

1
[[1,3], [2,6], [8,10], [15,18]]

如果不排序，区间之间的关系很散。你不知道当前区间后面还会不会突然冒出来一个更靠前的区间。合并的时候就容易变成到处找、到处比。

排序之后，区间会按左端点从小到大排好：

1
[[1,3], [2,6], [8,10], [15,18]]

这个例子原本就是排好的。换成题目里的示例 3：

1
[[4,7], [1,4]]

排完就会变成：

1
[[1,4], [4,7]]

这一步很关键。因为区间已经按起点排好，后面的区间起点只会越来越大。于是我们只需要盯着当前结果里的最后一个区间，看它能不能和新来的区间合并。

2. sort 比较 vector<int> 时到底比什么#

如果直接写：

1
sort(intervals.begin(), intervals.end());

这里 intervals 的类型是 vector<vector<int>>，也就是里面每个元素都是一个 vector<int>，比如 [1,3]、[2,6]。

C++ 在比较两个 vector<int> 的时候，默认用的是字典序比较。可以简单理解成：

1. 先比较第一个元素；
2. 如果第一个元素不同，小的排前面；
3. 如果第一个元素相同，再比较第二个元素；
4. 继续类推。

所以：

1
[1,3] < [2,6]   // 因为 1 < 2
2
[1,4] < [1,5]   // 第一个都是 1，再比第二个，4 < 5
3
[1,10] < [2,0]  // 只要第一个 1 < 2，后面 10 和 0 就不用管了

对这道题来说，每个区间就是 [start, end]。默认比较刚好会先按 start 排，如果 start 相同，再按 end 排。这已经满足合并区间的需求，所以不用专门写比较函数。

当然，如果想写得更显式，也可以这样：

1
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
2
    return a[0] < b[0];
3
});

但这题里直接默认排序就够了。少写一段 lambda，也算给手指放半天假。

3. 排好以后怎么合并#

排序之后，我们维护一个答案数组 merged。

每次拿到一个新区间，先取出它的左右端点：

1
int L = intervals[i][0], R = intervals[i][1];

然后只看 merged 里的最后一个区间：

• 如果 merged 为空，直接放进去；
• 如果 merged.back()[1] < L，说明最后一个区间的右端点已经小于当前左端点，不重叠，直接放进去；
• 否则说明两个区间有交集，更新最后一个区间的右端点。

合并时这一句最核心：

1
merged.back()[1] = max(merged.back()[1], R);

比如 [1,3] 遇到 [2,6]，因为 2 <= 3，它们重叠，合并成 [1,6]。

再比如 [1,4] 遇到 [4,5]，因为题目里这种也算重叠。此时 merged.back()[1] < L 不成立，也就是 4 < 4 不成立，所以走合并逻辑，最后合并成 [1,5]。

这里排序带来的好处就出来了：如果当前区间和最后一个结果都不重叠，那它更不可能和更前面的结果重叠。因为更前面的区间终点已经被处理完了，当前区间的起点又只会往右走。

4. C++ 写法#

1
class Solution {
2
public:
3
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
4
        if (intervals.size() == 0) {
5
            return {};
6
        }
7
        sort(intervals.begin(), intervals.end());
8
        vector<vector<int>> merged;
9
        for (int i = 0; i < intervals.size(); ++i) {
10
            int L = intervals[i][0], R = intervals[i][1];
11
            if (!merged.size() || merged.back()[1] < L) {
12
                merged.push_back({L, R});
13
            }
14
            else {
15
                merged.back()[1] = max(merged.back()[1], R);
16
            }
17
        }
18
        return merged;
19
    }
20
};

这份代码最舒服的地方是，真正的合并逻辑很短。不是因为题目自己简单到没有内容，而是排序已经把局面整理好了。

5. 我这次记下的东西#

这题我主要记两个点。

第一，std::sort 对 vector<int> 的默认比较是字典序。对于 [start, end] 这种区间，它天然就是先按 start 排，再按 end 排。

第二，合并区间的核心不是到处找重叠，而是先排序，让可能重叠的区间挨在一起。这样遍历时只需要看答案里的最后一个区间：能接上就延长，接不上就另开一段。

复杂度主要花在排序上，时间复杂度是 O(n log n)；合并遍历一遍是 O(n)。额外空间如果不算返回结果就是 O(1)，算上返回的 merged 就是 O(n)。