题解 | #合并区间#

/**
 * 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) {
        if (intervals.size() <= 1) {
            return intervals;
        }
        // 排序,按左端点排序，若左端点相同，则右端点较小的排列在前
        sort(intervals.begin(), intervals.end(), [=](Interval a, Interval b) {
            if (a.start != b.start) {
                return a.start < b.start;
            }
            return a.end < b.end;
        });
        vector<Interval> res;
        int l = intervals[0].start, r = intervals[0].end, i = 1;
        while (i < intervals.size()) {
            // 合并后区间没有变化
            if (l <= intervals[i].start && r >= intervals[i].end) {
                i++;
                continue;
            }
            if (intervals[i].start <= r) {
                r = intervals[i].end;
            } else {
                res.emplace_back(Interval(l, r));
                l = intervals[i].start;
                r = intervals[i].end;
            }
            i++;
        }
        res.emplace_back(Interval(l, r));
        return res;
    }
};