/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代碼中的類(lèi)名、方法名、參數(shù)名已經(jīng)指定，請(qǐng)勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param intervals Interval類(lèi)vector 
     * @return Interval類(lèi)vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        auto cmp = [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        };
        if (intervals.empty()) {
            return {};
        }
        sort(begin(intervals), end(intervals), cmp);
        vector<Interval> result;
        Interval cur;
        cur.start = intervals[0].start;
        cur.end = intervals[0].end;
        for (int i = 1; i < intervals.size(); ++i) {
            int s = intervals[i].start;
            int e = intervals[i].end;
            if (s <= cur.end) {
                // 重疊
                cur.end = max(cur.end, e);
            } else {
                // 不重疊
                result.emplace_back(cur.start, cur.end);
                cur.start = s;
                cur.end = e;
            }
        }
        result.emplace_back(cur.start, cur.end);
        return result;
    }
};