题解 | #合并区间#

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

思路：排序后遍历。

用tmp记录当前合并的区间，然后遍历排序后的区间集合，合并能合并的，否则记录到res数组并将tmp设置为当前区间。