Insert Interval

You get a list of intervals. Each interval is a pair [starti, endi]. The list is sorted by start, and no two intervals overlap.

You also get one more interval, newInterval = [start, end].

Add newInterval to the list. Merge it with every interval it overlaps. Return a list of the resulting intervals, still sorted by start and with no overlaps.

Two intervals overlap if they share at least one point. Intervals that only touch count too. For example, [0,3] and [3,5] share the point 3. They become [0,5].

Example 1:

Input: intervals = [[2,4],[7,9],[12,15]], newInterval = [8,13]
Output: [[2,4],[7,15]]
Explanation: [8,13] overlaps [7,9] and [12,15].
The three become [7,15].
[2,4] ends before 8. It stays as it is.

Example 2:

Input: intervals = [[1,2],[6,8]], newInterval = [3,5]
Output: [[1,2],[3,5],[6,8]]
Explanation: [3,5] fits in the gap between [1,2] and [6,8].
Nothing merges.

Example 3:

Input: intervals = [[0,3],[5,6]], newInterval = [3,5]
Output: [[0,6]]
Explanation: [3,5] touches [0,3] at 3.
It also touches [5,6] at 5.
All three join into one.

Constraints:

• 0 to 100,000 intervals in intervals. The list can be empty.
• Each start and end, in intervals and in newInterval, is from 0 to 1,000,000.
• No start is greater than its end.
• intervals is sorted by start.
• Each interval ends before the next one starts (endi < starti+1). They don't even touch.