描述

给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。

数据范围：区间组数 0 \le n \le 2 \times 10^50≤n≤2×105，区间内 的值都满足 0 \le val \le 2 \times 10^50≤val≤2×105
要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
进阶：空间复杂度 O(val)O(val)，时间复杂度O(val)O(val)

示例1

输入： 
[[10,30],[20,60],[80,100],[150,180]]
复制
返回值： 
[[10,60],[80,100],[150,180]]
复制

示例2

输入： 
[[0,10],[10,20]]
复制
返回值： 
[[0,20]]

解题思路：
注意各种全包含、半包含、边界值的判断 

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) {return a.start < b.start;});
        vector<Interval> res;
        int n = intervals.size();
        int i = 0;
        while (i < n-1) {
            Interval tmp;
            tmp.start = intervals[i].start;
            tmp.end = intervals[i].end;
            while (i < n-1 && (tmp.end >= intervals[i+1].start || tmp.start == intervals[i+1].start)) {
                tmp.end = max(tmp.end, intervals[i+1].end);
                i++;
            }
            res.push_back(tmp);
            i++;
        }
        if (i == n - 1) {
            res.push_back(intervals[n-1]);
        }
        return res;
    }
};