dsa · medium
Insert Interval
intervals is a list of disjoint [start, end] ranges, sorted by start. Insert new_interval and merge any overlaps so the result is again disjoint and sorted.
Arguments
intervals— sorted disjoint [start, end] rangesnew_interval— the [start, end] range to insert
Example
intervals = [[1,3],[6,9]], new_interval = [2,5] → [[1,5],[6,9]].
Constraints
0 <= intervals.length <= 10^4 intervals[i].length == 2 intervals is sorted by start and pairwise disjoint Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [[1,3],[6,9]] [2,5] Expected: [[1,5],[6,9]]
Example 2
Input: [[1,2],[3,5],[6,7],[8,10],[12,16]] [4,8] Expected: [[1,2],[3,10],[12,16]]