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] would result in
[1,2],[3,5],[6,7],[8,10],[12,16], insert and merge
[4,9] would result in
This is because the new interval
[4,9] overlaps with
Make sure the returned intervals are also sorted.
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.