You are given an array of non-overlapping intervals
intervals[i] = [starti, endi] represent the start and the end of the
ith interval and
intervals is sorted in ascending order by
starti. You are also given an interval
newInterval = [start, end] that represents the start and end of another interval.
intervals such that
intervals is still sorted in ascending order by
intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
intervals after the insertion.
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervalsis sorted by
startiin ascending order.
newInterval.length == 2
0 <= start <= end <= 105
Time complexity: O(N)
Space complexity: O(1)