题目

给定一个由若干区间组成的数组 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] 可以视为重叠区间，合并成 [1, 5]。

---

提示

• 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() , [](auto& v1 , auto& v2){return v1[0] < v2[0];});

        vector<vector<int>> res;

        int start = intervals[0][0] , end = intervals[0][1];
        for(auto& v : intervals) {
            // 对于一个新的区间,判断是否能接续在当前维护的区间 并且延长区间的右的端点

            // 无法接续
            if(v[0] > end) {
                res.push_back({start , end});
                start = v[0] , end = v[1];
            } else { // 可以接续
                end = max(end , v[1]);
            }
        }
        res.push_back({start , end});
        return res;
    }
}