题解 | #合并区间#

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    //定义一个比较器
    //按照start从小到大排序
   static bool cmp(Interval a,Interval b){
        return a.start<b.start;
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(), intervals.end(),cmp);//按照start从小到大排序
        vector<Interval> res;//结果数组
        if(intervals.size()<=0)
            return res;
        if(intervals.size()==1){
            return intervals;
        }
        //这两个变量暂存当前区间的左右边界大小
        int start=intervals[0].start;
        int end=intervals[0].end;
        for(int i=1;i<intervals.size();i++){
            int leftP=intervals[i].start;
            int rightP=intervals[i].end;
            if(leftP>=start&&leftP<=end){//说明这两个区间是有交集的，也即可以合并这两个区间
                end=end>rightP?end:rightP;//更新区间的右边界
            }
            else{//说明这两个区间并无交集，此时可以把[start,end]这个区间放入res中了
                Interval tmp(start,end);
                res.push_back(tmp);
                //此时最新区间应该是intervals[i]这个区间的左右边界
                start=intervals[i].start;
                end=intervals[i].end;
            }
        }
        //最后还要把[start,end]这个区间放进去
        Interval tmp(start,end);
        res.push_back(tmp);
        return res;
    }
};