Insert Into Disjoint Intervals

You are given an array intervals of closed intervals [start, end] that is already sorted ascending by start and in which no two intervals overlap, plus one further interval newInterval. Two intervals overlap when they share at least one point, so intervals that merely touch at an endpoint (for example [1, 3] and [3, 7]) must be merged.

Insert newInterval into the set, merging it with every interval it overlaps.

Return the resulting set, still sorted ascending by start and still pairwise non-overlapping.

Examples

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps [1,3], so the two merge into [1,5]. [6,9] begins after 5 and is unaffected.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] overlaps [3,5], [6,7] and [8,10], so all four merge into [3,10]. [1,2] ends before 4 and [12,16] begins after 10.

Example 3

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation: There is nothing to merge with, so the new interval is the whole answer.