leetcode: Insert Interval

Problem Description:

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 and Precautions:

Binary search the position of the starting point and the ending point of the new interval. The position is not necessary inside some interval in the sorted sequence but also possible to be in the space between two intervals, that is like [3, 5]  [8, 9], it could be in [3, 5], [8, 9], but also possible in (5, 8). Find the right position is not that tricky since the sorted intervals are non-overlapping with any other. Then according to the inserted positions say [A, B], merge all the possible intervals inside this interval (could be zero). Total time is O(logN)

Tips and Divergent thinking:

Note we need to keep the resulted sequence sorted as well.

Written on June 12, 2013