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.
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
Input: intervals =
[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval =
[4,8]Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
This problem is very familiar with problem 56. So we use the easiest way, we just use the code of problem 56. We can just put the new interval to the end of the intervals array. Then we call the merge function from problem 56.
Running time is 3ms only faster than 24.68% Java submissions, I think it is acceptable. If we want to solve this problem carefully, I think we need to find the first overlapping interval, then try to merge it and the next one, until there is no overlapping interval left. It is not very hard and maybe faster than the current solution.
To find other sort problems, see also Sort algorithms and problems.