题解 | #合并区间#

思路

1、首先根据起点排序
2、一个指针指向要检验的区间，一个对象代表已经合并好的区间，一直合并二者，知道他们不能合并，此时将合并好的区间存放进去，然后更新指针和区间
3、注意越界情况和最后一段区间的保存问题

代码

/**
 * 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>();}
        // 首先根据起点排序
        sort(intervals.begin(), intervals.end(), [=](const Interval& a, const Interval& b){return a.start<b.start;});

        // 一个指针指向需要判断是否合并的区间，之前有一个区间代表已经合并好的
        vector<Interval> res;
        Interval tmp = intervals[0];
        int p = 1;
        while(p<intervals.size()){
            while(p<intervals.size() && intervals[p].start<=tmp.end){
                tmp.start = min(tmp.start, intervals[p].start);
                tmp.end = max(tmp.end, intervals[p].end);
                p++;
            }

            if(p>=intervals.size()){        // p越界了
                res.push_back(tmp);
                return res;
            }
            res.push_back(tmp);
            tmp = intervals[p];
            p++;
        }

        res.push_back(tmp);

        return res;


    }
};