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.
[1,3],[6,9], insert and merge
[2,5] in as
[1,2],[3,5],[6,7],[8,10],[12,16], insert and merge
[4,9] in as
This is because the new interval
[4,9] overlaps with
# How to solve
I can solve this problem by using blute force searching. If I can find the interval which can be merge with newInterval, I update the newInterval and delete the interval. Then I insert the newInterval into the propare position and I can get solution by O(n).