/**
 * 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 {
private:
    void quicksort(vector<Interval> & datas,int left,int right)
    {
        if(left>=right) 
            return;
        int l=left;
        int r=right;
        int m=datas[(l+r)/2].start;
        while(l<=r)
        {
            while(datas[l].start<m) l++;
            while(datas[r].start>m) r--;
            if(l>right || r<left || l>=r)
                break;
            
            Interval tmp=datas[l];
            datas[l]=datas[r];
            datas[r]=tmp;
            l++;r--;
        }
        
        quicksort(datas,left,l-1);
        quicksort(datas,r+1,right);
    }
    inline bool checkoverlap(const Interval& interval1,const Interval& interval2)
    {
        if(interval1.start<=interval2.start && interval1.end>=interval2.end) return true;
        if(interval1.start<=interval2.start && interval1.end>=interval2.start) return true;
        if(interval1.start<=interval2.end && interval1.end>=interval2.end) return true;
        return false;
    }
    inline void mergeinterval(Interval& interval1,const Interval& interval2)
    {
        if(interval1.start>interval2.start) interval1.start=interval2.start;
        if(interval1.end<interval2.end) interval1.end=interval2.end;
    }
public:
    vector<Interval> merge(vector<Interval> &intervals) 
    {
        vector<Interval> v;
        if(intervals.size()==0) return v;
        
        //sort by start
        quicksort(intervals,0,intervals.size()-1);
        //merge
        
        int index=0;
        v.push_back(intervals[0]);
        
        for(int i=1;i<intervals.size();i++)
        {
            if(checkoverlap(v[index],intervals[i]))
            {
                mergeinterval(v[index],intervals[i]);
            }
            else
            {
                v.push_back(intervals[i]);
                index++;
            }
        }
        
        return v;
    }
};