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 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 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 .
Note that you don't need to modify intervals in-place. You can make a new array and return it.
0 <= intervals.length <= 10 ^4intervals[i].length == 20 <= start _i <= end _i <= 10 ^5intervals is sorted by start _i in ascending order.newInterval.length == 20 <= start <= end <= 10 ^5