Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:

Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Three cases to consider:

1. current [5,7] and new [1,2], since current.start>new.end, add new to results
2. current [1,2] and new [3,5], since current.end<new.start, add current to results
3. current [1,7] and new [2,3], since current.end>new.start, merge Interval.

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> results = new ArrayList<Interval>();
        if (intervals==null) {
            return results;
        }

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

        results.add(newInterval);       
        return results;        
    }