题目描述:

Given a collection of intervals, merge all overlapping intervals.

For example,

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

合并(闭)区间, 区间以对象的形式给出. 首先将输入的区间数组按照start从小到大排序, 然后先取第一个元素放入结果集中, 从第二个元素开始遍历. 取当前区间为cur, 结果集中的最后一个元素为pre. 如果cur.start > pre.end, 说明cur与pre并无交集, 由于有序, 所以cur以后的区间与pre也都没有交集, 所以可以将cur放入结果集中. 如果cur.start <= pre.end, 说明有交集, 由于必然存在cur.start >= pre.start, 所以新区间的start等于pre.start, 只要考虑cur.end与pre.end的大小关系, 如果cur.end <= pre.end, 那么新区间与pre相同; 如果cur.end > pre.end那么要把pre也就是结果集的最后一个区间的end修改为cur.end.

/**
* 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) {
        vector<Interval> ret;
        if(intervals.empty()) return ret;
        sort(intervals.begin(), intervals.end(), [=](Interval &a, Interval &b){
            return a.start < b.start;
        });
        ret.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++){
            Interval cur = intervals[i], pre = ret.back();
            if(cur.start > pre.end){
                ret.push_back(cur);
            }
            else{
                if(cur.end > pre.end){
                    ret.back().end = cur.end;
                }
            }
        }
        return ret;
    }
};