You are given an array of non-overlapping intervals sorted in ascending order by start time, and a single newInterval to insert. Insert the new interval into the list, merging any overlapping intervals as needed, and return the resulting array of non-overlapping intervals, still sorted by start time.
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Explanation: The new interval [2,5] overlaps with [1,3], so they merge into [1,5]. [6,9] is untouched.
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 with [3,5], [6,7], and [8,10], which all merge into [3,10].
0 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^5newInterval.length == 20 <= newInterval[0] <= newInterval[1] <= 10^5intervals = [[1, 3], [6, 9]], newInterval = [2, 5]