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 first so the min start always in the first of the list.

Then compare the end with the next start, if smaller, add it, otherwise merge the two intervals.

public List<Interval> merge(List<Interval> intervals) {
        List<Interval> results = new ArrayList<Interval>();
        if (intervals==null|intervals.isEmpty()) {
            return results;
        }

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

        int index = 1;
        Interval previousInterval = intervals.get(0);
        while(index<intervals.size()) {
            Interval currentInterval = intervals.get(index);
            if (previousInterval.end<currentInterval.start) {
                results.add(previousInterval);
                previousInterval = currentInterval;
            } else {
                Interval mergedInterval = new Interval(previousInterval.start, Math.max(previousInterval.end, currentInterval.end));
                previousInterval = mergedInterval;
            }
            index++;
        }
        results.add(previousInterval);
        return results;
    }