Insert Interval

Problem

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

Solution

/**
 * 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 List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        int i = 0;
        while (i < intervals.size() && intervals.get(i).end < newInterval.start) i++;
        while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
            Interval old = intervals.get(i);
            newInterval.start = Math.min(old.start, newInterval.start);
            newInterval.end = Math.max(old.end, newInterval.end);
            intervals.remove(i);
        }
        intervals.add(i, newInterval);
        return intervals;

    }
}

Analysis

Pretty straightforward solution
What we need to is to first find the first possible position where we can insert newInterval
We use while loop with condition intervals.get(i).end < newInterval.start
As long as the above statement returns true, we know that we cannot insert it at position i
Then as long as intervals.get(i).start <= newInterval.end, we know there is some room to insert
Instead of directly updating the intervals.get(i), we modify the newInterval with smaller start and larger end
And then we remove intervals.get(i)
At the end, we insert the newInterval into index i