题解 | #合并区间#

/**
 * 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) {
        // write code here
        int n = intervals.size();
        vector<Interval> ans;
        if(n==0)
            return ans;
        sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){
                if(a.start!=b.start)
                    return a.start<b.start;
                else
                    return a.end < b.end;
        });

        int start = intervals[0].start;
        int end = intervals[0].end;

        for(auto interval:intervals)
        {
            // cout << start << ", " << end << ", " << interval.start << ", " << interval.end << endl;
            // 没有交集
            if(end < interval.start)
            {
                ans.emplace_back(Interval(start,end));
                // 新的开始
                start = interval.start;
                end = interval.end;
            }
            // 有交集
            else
             {
                start = min(start, interval.start);
                end = max(end, interval.end); 
             };
            
        }

        // intervals 最后的一个位置比较后单独处理
        ans.emplace_back(Interval(start,end));

        return ans;
    }
};