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

MergeInterval.java

public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
    ArrayList<Interval> list = new ArrayList<Interval>();
    Collections.sort(intervals, new Comparator<Interval>(){
        public int compare(Interval x, Interval y) {
            if (x.start == y.start)
                return x.end - y.end;
            else
                return x.start - y.start;
        }
    });
    
    for (int i=0; i<intervals.size(); i++){
        Interval x = intervals.get(i);
        
        while (i+1 < intervals.size() && intervals.get(i+1).start <= x.end){
            x.end = Math.max(x.end, intervals.get(i+1).end);
            i++;
        }
        list.add(x);
        
    }
    return list; 
}