题解 | #合并区间#

第一步 排序(start排序完, 在逆序排end)
[1,3], [1,2], [2,6], [2,4], [8,10],[15,18]

分两种情况合并区间
情况1: [1,2], [2,5] 则更新最后一组的end为5, 即[1,5]
情况2: [1,2], [4,8] 则直接插入[4,8]

class Solution {
public:
    struct myC{ // 按照第二位进行排序
        bool operator()(Interval &a, Interval &b){
            return a.start < b.start || (a.start==b.start && a.end>b.end); 
        }
    };
    // 第一种情况 [1.4], [2,8] 则更新为[1,8]
    // 第二种情况 [1,4], [6,10] 则插入[6,10]
    vector<Interval> merge(vector<Interval> &nums) {
        if(nums.empty()) return {};
        sort(nums.begin(), nums.end(), myC());
        vector<Interval> ans;
        ans.emplace_back(nums[0]);
        for(int i=1, n=nums.size(); i<n; i++){
            if(ans.back().end >= nums[i].start && ans.back().end < nums[i].end){
                ans.back().end = nums[i].end;
            }else if(ans.back().end < nums[i].start){
                ans.emplace_back(nums[i]);
            }
        }
        return ans;
    }
};