力扣56.合并区间

题目描述：

以数组?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 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路：

这个题可以说是非常经典的区间问题了。题目求的是把有交集的区间合并，最后得到的区间任意两个都没有交集。

为了让有交集的两个区间相邻，我们对区间的左端点从小到大进行排序。这样一来，有交集的两个区间一定相邻，而相邻两个区间没有交集的话就说明后面的区间和前面的区间一定没有交集。

用l,r来维护一个区间，这个区间是可以合并的最大区间，遍历排序好的数组，如果当前的区间的左端点>r,说明出现了新的区间，否者说明目前遍历到的区间与[l,r]有至少一个元素的交集，这个时候并没有出现新区间，假设l=2,r=6,此时遍历到了区间[3,7],我们只需要看是否要扩大当前维护的区间，r=max(r,7),那么维护的区间就变成了[2,7]。

代码：

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> ans;
    sort(intervals.begin(), intervals.end());//默认以左端点从小到大排序
    int r = -1e9;
    int l = -1e9;//第一个区间一定更新l,r.
    for (auto it : intervals) {
        if (it[0] > r) {//如果这个区间的左端点在维护区间右端点的右边
            l = it[0];
            r = it[1];
            ans.push_back({ l,r });//把新区间放入答案数组中
        }
        else {
            if (r < it[1]) {//当前区间与维护区间有交集，并且右端点大于r,更新右端点
                r = it[1];
                ans[ans.size() - 1][1] = r;//更新这个新区间的右端点
            }
        }
    }
    return ans;