Insert and Merge an Interval
Problem statement
You are given a list of intervals intervals, where each interval [start, end] covers every point from start to end, both ends included. The list is sorted by start, and no two intervals overlap or touch.
Add one more interval, newInterval. Then join every group of intervals that overlap or share an endpoint into one interval, and return the result sorted by start.
For example, [1, 2] and [2, 5] share the point 2 and become [1, 5], but [1, 2] and [3, 5] stay separate.
Function
insertInterval(intervals: int[][], newInterval: int[]) → int[][]Examples
Example 1
intervals = [[2,4],[9,12]]newInterval = [5,8]return = [[2,4],[5,8],[9,12]][5, 8] overlaps nothing: 4 < 5 and 8 < 9. It just goes between the two existing intervals.
Example 2
intervals = [[1,2],[4,6],[8,10]]newInterval = [2,8]return = [[1,10]][2, 8] shares the point 2 with [1, 2], covers [4, 6], and shares the point 8 with [8, 10]. All four join into [1, 10].
Example 3
intervals = []newInterval = [3,3]return = [[3,3]]There are no intervals yet, so the answer is just the new one. A single point [3, 3] is a valid interval.
Constraints
0 <= intervals.length <= 1000intervals[i].length == 2andnewInterval.length == 20 <= start <= end <= 10^5for every interval, includingnewIntervalintervalsis sorted by start, and each interval ends strictly before the next one starts (intervals[i][1] < intervals[i + 1][0]).