区间合并

typedef pair<int, int> PII;

bool cmp(vector<int> &a, vector<int> &b)
{
    return a[0] < b[0];
}

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        PII initial = {-1e9, 1e9};
        vector<vector<int>> ans;
        int maxRight = -1e9;
        sort(intervals.begin(), intervals.end(), cmp);
        for(int i = 0; i < intervals.size(); i++)
        {
            int left = intervals[i][0];
            int right = intervals[i][1];
            maxRight = max(maxRight, right);
            if(right < maxRight) continue;
            if(initial.first == -1e9)
            {
                initial.first = left;
                initial.second = right;
                continue;
            }
            if(initial.second <= right && initial.second >= left)
            {
                initial.second = max(initial.second, right);
            }
            else
            {
                ans.push_back({initial.first, initial.second});
                initial = {-1e9, 1e9};
                i --;
            }

        }
        if (initial.first != -1e9)
        {
            ans.push_back({initial.first, initial.second});
        }
        return ans;
    }

};