The list intervals holds time slots that do not overlap, sorted by their start. Each slot [start, end] runs from start to end. You are also given one more slot, newInterval.
Add newInterval to the list. If it overlaps some slots, merge them with it into one slot. The final list must stay sorted by start and must have no overlaps. Return the final list.
Examples
Example 1:
Input: intervals = [[2,4],[8,10]], newInterval = [5,7]
Output: [[2,4],[5,7],[8,10]]
Explanation: The new slot [5,7] overlaps nothing. It goes between the two old slots.
Example 2:
Input: intervals = [[1,3],[5,8],[9,12],[15,18]], newInterval = [6,10]
Output: [[1,3],[5,12],[15,18]]
Explanation: [6,10] overlaps [5,8] and [9,12]. All three merge into [5,12].
Example 3:
Input: intervals = [], newInterval = [4,6]
Output: [[4,6]]
Explanation: The list is empty, so the new slot is the whole answer.