题解 | #合并区间#

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类vector 
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {

        //按各区间start升序排序
        sort(intervals.begin(),intervals.end(),
        [](const Interval& a,const Interval& b)->bool{return a.start<b.start;});

        auto p = intervals.begin();
        auto q = p + 1;
        vector<Interval> v;
        int s,e;
        s = p->start;
        e = p->end;
        while(p!=intervals.end()){
            if(e>=q->start&&q!=intervals.end()){//若两区间相交，且q不为尾迭代器，求并集

                if(q->end > e)
                    e = q->end;
                q++;//继续检查p所指区间与更后方区间是否相交

            }else{//若两区间不相交，或q为尾迭代器，将p所指区间存入

                auto copy = *p;
                copy.start = s;
                copy.end = e;
                v.push_back(copy);

                p = q;
                s = p->start;
            e = p->end;
                q++;

            }
        }

        return v;

    }
};