Merge Intervals

LeetCode #56

Description:

Given a collection of intervals, merge all overlapping intervals.

Example:

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

Idea:

这题比insert interval要简单不少，也可以调用insert interval的函数，但是没必要。如果不overlap，直接推入result，如果overlap，更新end就行。

Code:

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        if(intervals.size()<=1) return intervals;

        struct CMP{
          bool operator() (const Interval& a, const Interval& b) const{
              return a.start<b.start;
          }  
        };

        sort(intervals.begin(), intervals.end(), CMP{});

        vector<Interval> result;
        result.push_back(intervals[0]);

        for(int i=1; i<intervals.size(); ++i){
            if(intervals[i].start>result.back().end){
                result.push_back(intervals[i]);
            }
            else{
                if(result.back().end<intervals[i].end)
                    result.back().end=intervals[i].end;
            }
        }

        return result;

    }
};