Merge Intervals

来源：Leetcode

原帖：http://oj.leetcode.com/problems/merge-intervals/

题目：
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].
Solution: Sort in ascending order of 'start'. Traverse the 'intervals', merge or push...

代码：

 /**  
  * Definition for an interval.  
  * struct Interval {  
  *   int start;  
  *   int end;  
  *   Interval() : start(0), end(0) {}  
  *   Interval(int s, int e) : start(s), end(e) {}  
  * };  
  */  
 bool compare(const Interval& a, const Interval& b) {  
   return a.start < b.start;  
 }  
   
 class Solution {  
 public:  
   vector<Interval> merge(vector<Interval> &intervals) {  
     int N = intervals.size();  
     if (N <= 1) return intervals;  
     sort(intervals.begin(), intervals.end(), compare);  
     vector<Interval> res;  
     Interval last = intervals[0];  
     for (int i = 1; i < N; ++i) {  
       if (intervals[i].start > last.end) {  
         res.push_back(last);  
         last = intervals[i];  
       } else {  
         last.end = max(last.end, intervals[i].end);  
       }  
     }   
     res.push_back(last); // push back the last one  
     return res;  
   }  
 };