Description：

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

Code：

int partition(vector
     
      & intervals, int low, int high)    {        Interval key(intervals[low].start, intervals[low].end);        while (low
      
       =key.start)--high;            intervals[low].start = intervals[high].start;            intervals[low].end = intervals[high].end;                        while (low < high && intervals[low].start<=key.start)++low;            intervals[high].start = intervals[low].start;            intervals[high].end = intervals[low].end;        }            intervals[low].start = key.start;            intervals[low].end = key.end;            return low;    }    void quickSort(vector
       
        & intervals, int low, int high)    {        if (low < high)        {            int pos = partition(intervals,low,high);            quickSort(intervals, low, pos);            quickSort(intervals, pos+1,high);        }    }    void quickSort(vector
        
         & intervals){        quickSort(intervals,0,intervals.size()-1);    }    vector
         
           merge(vector
          
           & intervals) { vector
           
            result; quickSort(intervals); unsigned int n = intervals.size(); if (n==0) return result; result.push_back(intervals[0]); for (int i = 1; i < n; ++i) { int temp = result.size(); if (intervals[i].start <= result[temp-1].end) result[temp-1].end = max(intervals[i].end,result[temp-1].end); else result.push_back(intervals[i]); } return result; }