Merge Overlapping 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].

 /**  
  * 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:  
   static bool compare(Interval i1, Interval i2){  
     return (i1.start < i2.start);  
   }  
   vector<Interval> merge(vector<Interval>& intervals) {  
     vector<Interval> out;  
     int n = intervals.size();  
     if(n <= 0){  
       return out;  
     }  
     //sort as per the start time  
     sort(intervals.begin(), intervals.begin() + n, compare);  
     stack<Interval> it;  
     it.push(intervals[0]);  
     for(int i = 1; i < n; i++){  
       Interval topInterval = it.top();  
       //if start time of next is after the end of the prev, push the next  
       if(intervals[i].start > topInterval.end){  
         it.push(intervals[i]);  
       }else if(intervals[i].end > topInterval.end){  
         //if start time of next is before the end of the prev and the end of the next is after the end of the prev, then update the end of the prev  
         topInterval.end = intervals[i].end;  
         it.pop();  
         it.push(topInterval);  
       }  
     }  
     vector<Interval> out;  
     while(!it.empty()){  
       Interval curr = it.top();  
       out.push_back(curr);  
       it.pop();  
     }  
     return out;  
   }  
 };