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: 1. Sort in ascending order of 'start'.

2. Traverse the 'intervals', merge or push...

1 /** 2  * Definition for an interval. 3  * struct Interval { 4  *     int start; 5  *     int end; 6  *     Interval() : start(0), end(0) {} 7  *     Interval(int s, int e) : start(s), end(e) {} 8  * }; 9  */10 11 bool compare(const Interval &a, const Interval &b) 12 {13     return a.start < b. start;14 }15 class Solution {16 public:17     18     vector
     
       merge(vector
      
        &intervals) {19         vector
       
         res;20         int N = intervals.size(); 21         if(N <= 1) return intervals;22         sort(intervals.begin(), intervals.end(), compare);23         Interval last = intervals[0];24         for(int i = 1; i < N; i++) {25             if(intervals[i].start > last.end) {26                 res.push_back(last);27                 last = intervals[i];28             }29             else {30                 last.end = max(last.end, intervals[i].end);31             }32         }33         res.push_back(last);34         return res;35     }36 };