59. Insert Interval - Calendar Management

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

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.

Examples

insert([[1,3],[6,9]], [2,5]); // [[1,5],[6,9]]
// Insert [2,5] merges with [1,3] to form [1,5]

insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]); 
// [[1,2],[3,10],[12,16]]
// Insert [4,8] merges with [3,5], [6,7], and [8,10]