题解 | #合并区间#

方法：

1、将数组按照区间的起点从小到大的顺序进行排序；

2、对排序后数组遍历，如果后一个区间的起点不大于前面一个区间的末尾，说明这两个区间可以合并；否则就不能合并存入数组即可。

时间复杂度：o(nlog2​n)，排序的复杂度为o(nlog2​n)，后续遍历所有区间的复杂度为o(n)

空间复杂度：o(n)

class Solution {
  public:
  	// 重载
    static bool cmp(Interval& a, Interval& b) {
        return a.start < b.start;
    }
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval> res;
        if (intervals.size() == 0)
            return res;

        // 排序
        sort(intervals.begin(), intervals.end(), cmp);

        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (res.back().end >= intervals[i].start) {
                res.back().end = max(res.back().end, intervals[i].end);
            } else {
                res.push_back(intervals[i]);
            }
        }

        return res;
    }
};