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

思路就是找到要merge的n个区间，然后把这几个区间删掉，再把新的区间插进去。

s初始化为-1，s+1就是插入的位置。s记录的是要merge的区间的前一个区间，所以插入位置就是s+1。

i就是要merge的区间的后一个区间。

如果merge错的话，可能会出现output limit exceeded。

56ms。