合并区间

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

提示：

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

56.合并区间

2个区间的关系有6种，但是其实可以变成上面3种情况（只需要假设第一个区间的起始位置 <= 第二个区间的起始位置，如果不满足这个假设，交换这两个区间）。

所以按照起始位置对所有区间排序，再按照逻辑合并区间就行。逻辑很简单，懒得写了。不会真有人不知道吧

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){
            return a[0] < b[0];
        });
        int n = intervals.size();
        int left = intervals[0][0], right = intervals[0][1];
        for(int i = 1; i < n; ++i){
            if(right >= intervals[i][0]){
                right = max(right, intervals[i][1]);
            }else{
                ans.push_back({left, right});
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        ans.push_back({left, right});
        return ans;
    }
};