题解 | #合并区间#

思路

1、根据区间起点的大小，对区间排序
2、一个指针，指向当前考虑的区间元素，一个区间元素代表当前合并后的区间，也就是判断两个区间能否合并
3、对于能合并的，更新区间，更新指针；对于不能合并的，保存合并好的区间，将当前指针指向的区间设置为新的区间，指针向后移动1位
4、当指针越界以后，保存当前合并好的区间

代码

/**
 * 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:
    vector<Interval> merge(vector<Interval> &intervals) {
        if(intervals.empty()){
            return vector<Interval>(0);
        }

        sort(intervals.begin(), intervals.end(), 
                 [=](const Interval& a, const Interval& b){return a.start < b.start;});

        vector<Interval> res;

        int count = intervals.size();
        int cur = 1;
        auto before = intervals[0];
        while(cur<count){
            while(cur<count && intervals[cur].start <= before.end){
                before.start = min(before.start,intervals[cur].start) ;
                before.end = max(intervals[cur].end, before.end);
                cur++;
            }
            if(cur<count){
                res.push_back(before);
                // 创建新的before
                before = intervals[cur];
                cur++;
            }
//             else{            // 结束了
//                 res.push_back(before);

//             }


        }

        res.push_back(before);

        return res;
    }
};