合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]。

请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 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] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

排序-贪心合并：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        vector<vector<int>> ans;

        for (auto& interval : intervals)
        {
            if (ans.empty() || ans.back()[1] < interval[0])
            {
                ans.push_back(interval);
            }
            else
            {
                ans.back()[1] = max(ans.back()[1], interval[1]);
            }
        }

        return ans;
    }
};

核心思想

这题的关键是：先把所有区间按照左端点从小到大排序。

排序之后，区间的顺序就变得有规律了。

假设当前已经合并好的最后一个区间是：

[L, R]

现在要处理的新区间是：

[start, end]

因为数组已经按照左端点排序，所以新来的区间左端点 start 一定不会小于前面已经处理过的区间左端点。

接下来只需要判断：

start 是否大于当前合并区间的右端点 R。

如果：

start > R

说明新区间在当前区间右侧，并且中间有空隙，二者不重叠，需要把新区间单独加入答案。

如果：

start <= R

说明新区间和当前区间有交集，或者刚好首尾相接，需要合并。

合并后的新区间右端点是：

max(R, end)

所以更新：

ans.back()[1] = max(ans.back()[1], interval[1]);

为什么要先排序

如果不排序，区间之间的相对位置是混乱的。

例如：

intervals = [[8,10], [1,3], [2,6]]

如果直接从左到右处理，就可能先遇到 [8,10]，然后再遇到 [1,3]，很难只通过“上一个区间”判断是否应该合并。

排序之后变成：

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

这时所有可能和当前合并区间发生重叠的区间，一定会连续出现在它后面。

也就是说，只要当前新区间的左端点已经大于当前合并区间的右端点，那么后面区间的左端点只会更大，更不可能和当前合并区间重叠。

所以当前合并区间就可以安全地确定下来。

合并条件推导

考虑两个区间：

[a, b]

[c, d]

并且排序后有：

a <= c

也就是说，第一个区间的左端点不大于第二个区间。

两个区间不重叠的唯一情况是：

b < c

即第一个区间的右端点在第二个区间左端点之前。

如果不满足 b < c，也就是：

b >= c

那么两个区间就有重叠，或者至少端点相接。

题目中 [1,4] 和 [4,5] 也被视为重叠区间。

所以当：

b == c

时也要合并。

因此合并条件是：

c <= b

对应到代码就是：

ans.back()[1] >= interval[0]

代码里用反面条件判断不重叠：

if (ans.empty() || ans.back()[1] < interval[0])

只有当前答案为空，或者上一个合并区间的右端点严格小于新区间左端点时，才新开一个区间。

否则就合并。

为什么只需要和答案最后一个区间比较

排序后，答案中的区间也是按照左端点从小到大排列的。

当我们处理新区间 [start, end] 时：

• 它的左端点一定不小于之前所有区间的左端点
• 前面已经合并完成的区间之间互不重叠
• 唯一可能和它重叠的，只会是答案里的最后一个区间

为什么不可能和更早的区间重叠？

因为如果新区间能和更早的区间重叠，那么它也一定会跨过答案最后一个区间的位置。

但答案中更早区间和最后一个区间已经是不重叠的，并且更早区间在更左边。

如果新区间的左端点没有和最后一个区间重叠，那么它更不可能回头和更早区间重叠。

所以每次只比较 ans.back() 就够了。

正确性证明

我们证明：算法返回的区间数组不重叠，并且恰好覆盖输入中的所有区间。

结论 1：算法不会漏掉任何输入区间

算法会按排序后的顺序遍历每一个原始区间。

对于每个区间，只有两种处理方式：

1. 和当前答案最后一个区间不重叠，则直接加入答案。
2. 和当前答案最后一个区间重叠，则合并到最后一个区间中。

无论哪种情况，这个输入区间都会被答案中的某个区间覆盖。

所以算法不会漏掉任何输入区间。

结论 2：算法不会产生重叠区间

当新区间和答案最后一个区间不重叠时，才会执行：

ans.push_back(interval);

这个条件是：

ans.back()[1] < interval[0]

说明新区间在最后一个答案区间右侧，并且没有重叠。

由于答案中原本的区间已经互不重叠，新加入的区间也不和最后一个区间重叠，所以答案仍然保持互不重叠。

当新区间和最后一个区间重叠时，算法不会新增区间，而是扩展最后一个区间的右端点。

因此也不会额外制造重叠区间。

所以算法得到的答案始终互不重叠。

结论 3：重叠区间一定会被合并

排序后，如果当前区间 [start, end] 和答案最后一个区间 [L, R] 重叠，那么必有：

start <= R

算法会进入合并分支：

ans.back()[1] = max(ans.back()[1], interval[1]);

合并后的区间是：

[L, max(R, end)]

它正好覆盖原来的两个区间。

因此所有和当前合并区间重叠的后续区间都会被不断合并进去。

得出结论

由结论 1 可知，答案覆盖所有输入区间。

由结论 2 可知，答案中的区间互不重叠。

由结论 3 可知，所有重叠区间都会被正确合并。

所以算法返回的结果正确。

举例理解

以：

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

为例。

排序后顺序不变。

先加入：

[1,3]

然后处理：

[2,6]

因为：

2 <= 3

所以两个区间重叠，合并成：

[1,6]

继续处理：

[8,10]

因为：

6 < 8

所以不重叠，单独加入。

继续处理：

[15,18]

因为：

10 < 15

所以也单独加入。

最终答案是：

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

复杂度分析

设区间数量为 n。

排序需要：

O(n log n)

之后遍历所有区间一次，每个区间只处理一次，时间复杂度是：

O(n)

所以总时间复杂度是：

O(n log n)

答案数组最坏情况下需要存储所有区间，所以空间复杂度是：

O(n)

如果不把返回答案占用的空间计入额外空间，那么除排序递归栈外，额外空间可以看作 O(1)。