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

Sort the intervals by its start time, merge two if not first.end < second.start.

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals.size() <=1 ) return intervals;
        ArrayList<Interval> result = new ArrayList<>();

        Collections.sort(intervals, new Comparator<Interval>(){
           @Override
            public int compare(Interval i1, Interval i2){
                if(i1.start == i2.start){
                    return i1.end - i2.end;
                }else{
                    return i1.start - i2.start;
                }
            }
        });


        result.add(intervals.get(0));
        for(int i=1; i< intervals.size(); i++){
            Interval last = result.get(result.size()-1);
            Interval cur = intervals.get(i);
            if(last.end < cur.start){
                result.add(cur);
            }else{
                last.end = Math.max(last.end, cur.end);
            }
        }
        return result;
    }
}