Week2-Day4 ##排序##

我们将区间按左区间进行排序，然后比较l区间和r区间是否存在交集

当存在交集时，我们更新当前l区间的end值，直到区间不存在交集。
循环结束说明已经完成了一个区间的合并，我们将此时l区间存下来，并把l移动到r的位置开始下一个区间的合并

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类vector 
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        int l=0,r=0;
        vector<Interval>ans;
        //按照左区间排序，相同时排序较小的右区间
        sort(intervals.begin(),intervals.end(),[&](Interval&i,Interval&j){
            return i.start == j.start? i.end < j.end : i.start < j.start;
        });
        int n=intervals.size();
        while(r<n){
			//合并区间有交集的
            while(r<n && intervals[r].start <= intervals[l].end ){
                intervals[l].end=max(intervals[l].end,intervals[r].end);
                r++;
            }
            ans.push_back(intervals[l]);
            l=r;
        }
        return ans;
    }
};

周周打卡图粘贴处