O(n log n) 的时间和 O(1) 的额外空间。
题目链接
分析
对Interval类型的数组进行排序，然后再比较上一个的end是否大于下一个start。
程序
/** * Definition of Interval: * class Interval { * int start, end; * Interval(int start, int end) { * this->start = start; * this->end = end; * } * } */ class Solution { public: /** * @param intervals: interval list. * @return: A new interval list. */ //考察点：sort使用，新数据类型的使用 static bool cmp(const Interval &a, const Interval &b){ return (a.start < b.start); } vector<Interval> merge(vector<Interval> &intervals) { // write your code here vector<Interval> ans; if(intervals.empty())//是否为空 return ans; sort(intervals.begin(), intervals.end(), cmp);//安装start排序 ans.push_back(intervals[0]); for(int i = 1; i < intervals.size(); i++){ //上一个尾和下一个头比较 if(ans.back().end >= intervals[i].start){ ans.back().end = max(ans.back().end, intervals[i].end); } else ans.push_back(intervals[i]); } return ans; } };