Insert Interval
Given a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary.
Examples
Input: [[[1,3],[6,9]],[2,5]]
Output: [[1,5],[6,9]]
Input: [[[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8]]
Output: [[1,2],[3,10],[12,16]]
Hints
Initialize an empty result list to store the merged intervals.
Iterate through the intervals and add all intervals that end before the new interval starts to the result list.
For intervals that overlap with the new interval, merge them by updating the new interval's start to the minimum of the overlapping intervals' starts and the new interval's start, and the new interval's end to the maximum of the overlapping intervals' ends. Add the merged interval to the result list.
Related Problems
Insert Interval
Given a list of non-overlapping intervals sorted by start, insert a new interval and merge if necessary.