For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(intervals==null||intervals.size()<=1){
            return intervals;
        }
        //sort the intervals by the start time.
        //1. convert ArrayList to array
        Interval[] intervalArr = new Interval[intervals.size()];
        int index = 0;
        for(Interval interval:intervals){
            intervalArr[index++] = interval;
        }
        //2. use quick sort to sort intervals by the start time O(nlgn)
        sort(intervalArr,0,intervalArr.length-1);

        //3. only need to compare the new interval with the last interval in the sorted list
        ArrayList<Interval> merged = new ArrayList<Interval>();
        Interval last = intervalArr[0];
        for(int i=1;i<intervalArr.length;i++){
            if(last.end<intervalArr[i].start){
                merged.add(last);
                last = intervalArr[i];
            }else{
                Interval newInterval = new Interval(last.start, Math.max(last.end, intervalArr[i].end));
                last = newInterval;
            }
        }
        merged.add(last);

        return merged;
    }

    public void sort(Interval[] inters,int start, int end){
        int pivot = partition(inters, start, end);
        if(start<pivot-1){
            sort(inters, start, pivot-1);
        }
        if(pivot<end){
            sort(inters, pivot, end);
        }
    }

    public int partition(Interval[] inters, int start, int end){
        int middle = (start+end)/2;
        Interval pivot = inters[middle];

        int i=start;
        int j=end;
        while(i<=j){
            while(inters[i].start<pivot.start){
                i++;
            }

            while(inters[j].start>pivot.start){
                j--;
            }

            if(i<=j){
                swap(inters,i,j);
                i++;
                j--;
            }
        }

        return i;
    }

    public void swap(Interval[] inters, int i, int j){
        Interval tmp = inters[i];
        inters[i] = inters[j];
        inters[j] = tmp;
    }

}