intervals is a list of closed intervals [startᵢ, endᵢ], sorted by start, where no two of them share a point. Add one more interval, newInterval, and return the list that results: still sorted by start, and with no two intervals sharing a point.
Wherever newInterval overlaps or touches existing intervals, fuse them all into a single interval. Intervals it never meets stay exactly as they were. You may build and return a new list rather than changing intervals.
[5,8] runs into [7,10], and together they cover 5 to 10. It stops short of [2,4] and [13,15], so those are untouched.
[4,9] shares the point 4 with [3,4], swallows [6,6] and shares 9 with [9,12]. All four become [3,12].
[]
With nothing to merge into, the new interval is the whole answer.
Constraints
0 <= intervals.length <= 10⁴ (intervals may be empty)intervals[i].length == 20 <= startᵢ <= endᵢ <= 10⁵intervals is sorted by startᵢ in increasing order, and no two of its intervals share a point.newInterval.length == 20 <= newInterval[0] <= newInterval[1] <= 10⁵The list is already sorted and its intervals never touch each other, so it splits into three runs: the ones that end before newInterval starts, the ones that meet it, and the ones that start after it ends.
Draw the intervals on a number line, left to right, with a gap between each one and the next. Now lay newInterval on top of them. Every existing interval ends up in one of three places:
Time O(n)Space O(n)
The full walkthrough and code are part of Premium