题目描述

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

样例

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

算法

(排序) $O(n \log n)$

1. 首先将所有区间按照 start 排序，start 相同的按照 end 排序。
2. 从头开始遍历所有区间，并求他们的并集。定义 cur 表示当前一些区间的并集。
3. 若发现当前遍历到的区间 start 严格大于 cur 的 end，则当前并集需要加入到答案数组中，且更新区间并集 cur 为当前区间。
4. 若发现当前遍历到的区间 end 严格大于 cur 的 end，则更新 cur 的 end 为当前区间的 end。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$，排序后只需要线性扫描，故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(), intervals.end(),
            [&](const vector<int> &x, const vector<int> &y) {
                if (x[0] != y[0])
                    return x[0] < y[0];
                return x[1] < y[1];
            });

        vector<vector<int>> ans;

        if (n == 0)
            return ans;

        vector<int> cur = intervals[0];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] > cur[1]) {
                ans.push_back(cur);
                cur = intervals[i];
            } else if (intervals[i][1] > cur[1])
                cur[1] = intervals[i][1];
        }

        ans.push_back(cur);
        return ans;
    }
};