Monday, January 20, 2014

Insert Interval (Java)


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

      This question is very similar with merge intervals. because the intervals is initially sorted according to their start times, so what we should do is just go through every interval in intervals list and put the smaller un-overlap interval into result list and updated current newInterval until to the end. But do not forget to add last newInterval into result list. See code below