56. Merge Intervals（速度不理想，之后再看）

题意：

给一组范围，对这些范围进行合并，将结果输出。

举例：

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

思路：

根据逻辑暴力遍历，两个方法的速度都不理想，之后再想想

vector<Interval> merge(vector<Interval>& intervals) {
    //暴力 特别慢if (intervals.size() <= 1)return intervals;sort(intervals.begin(), intervals.end(), [&](Interval &a, Interval &b) {
    return a.start < b.start; });auto pre = intervals.begin();for (auto it = intervals.begin() + 1; it < intervals.end(); ) {
    if (pre->end >= it->start) {
    if (pre->end < it->end)pre->end = it->end;it = intervals.erase(it);}else {
    ++it;++pre;}	}return intervals;
}

vector<Interval> merge(vector<Interval>& intervals) {
    //50%int sz = intervals.size();if (intervals.size() <= 1)return intervals;sort(intervals.begin(), intervals.end(), [&](Interval &a, Interval &b) {
    return a.start < b.start; });vector<Interval> res;res.push_back(intervals[0]);for (int i = 1; i < sz; ++i) {
    if (intervals[i].start == res.back().start&&intervals[i].end > res.back().end)res.back().end = intervals[i].end;else if (intervals[i].start <= res.back().end) {
    if (intervals[i].end > res.back().end)res.back().end = intervals[i].end;elsecontinue;}else if (intervals[i].start > res.back().end)res.push_back(intervals[i]);}return res;
}