先按左边界从小到大排序,然后遍历所有区间,边比较边将区间推入结果,如果当前区间与结果的最后一个区间有重叠,更新结果中最后一个区间的边界,代码如下:
// // Created by jt on 2020/9/29. // #include <vector> using namespace std; class Solution { public: vector<Interval> merge(vector<Interval> &intervals) { vector<Interval> res; // 自定义排序函数(lambda函数) sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){ return a.start < b.start; }); for (int i = 0, j = 0; i < intervals.size(); ++i) { if (i != 0 && intervals[i].start <= res[j-1].end) { res[j-1].end = max(res[j-1].end, intervals[i].end); } else { res.push_back(intervals[i]); ++j; } } return res; } };