Insert Interval

Insert IntervalMar 27 '12

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

Algorithm idea

While traversing the input intervals, merge with all intervals conflicting with the new interval to be inserted. If there are no conflicting intervals, then find the correct position to insert this new interval based on the start value of the new interval relative to the intervals in the input interval vector.

Time Complexity: O(n)
Space Complexity: O(1)