You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and end of the i-th interval, and intervals is sorted in ascending order by start_i.
You are also given an interval newInterval = [start, end] that represents the interval to be inserted.
Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: The new interval [2,5] overlaps with [1,3]. Merging them gives [1,5]. The interval [6,9] does not overlap, so the result is [[1,5],[6,9]].
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: The new interval [4,8] overlaps with [3,5], [6,7], and [8,10]. Merging them gives [3,10].
Example 3:
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Explanation: There are no existing intervals, so just insert the new interval.
0 <= intervals.length <= 10⁴intervals[i].length == 20 <= start_i <= end_i <= 10⁵intervals is sorted by start_i in ascending ordernewInterval.length == 20 <= start <= end <= 10⁵