Insert an Interval
You get a list intervals. Each item is a pair [start, end] with start <= end. The list is sorted by start, and no two intervals in it overlap or touch.
You also get one more interval, newInterval.
Add newInterval to the list. If it overlaps other intervals, join all of them into one interval that covers them. Return the new list. It must still be sorted by start, and no two intervals in it may overlap.
Note
- Two intervals that share only an end point, such as
[2, 5]and[5, 9], count as overlapping. Join them. - Return a new list. The input list may be empty.
Hint: walk the list once. The intervals fall into three groups: the ones that end before newInterval starts, the ones that overlap it, and the ones that start after it ends.
Examples
Example 1
- Input:
- [[2,4],[7,9],[12,15]], [8,13]
- Output:
- [[2,4],[7,15]]
[8, 13] overlaps [7, 9] and [12, 15]. Together they cover 7 to 15. [2, 4] ends before 8, so it stays as it is.
Example 2
- Input:
- [[3,5],[10,11]], [6,8]
- Output:
- [[3,5],[6,8],[10,11]]
[6, 8] overlaps nothing. It goes between [3, 5] and [10, 11] so the list stays sorted.
Example 3
- Input:
- [[1,3],[6,9]], [3,6]
- Output:
- [[1,9]]
[3, 6] touches [1, 3] at 3 and [6, 9] at 6. Touching counts as overlapping, so all three join into [1, 9].
Constraints
0 <= intervals.length <= 120 <= start <= end <= 150intervalsis sorted bystart, and its intervals do not overlap or touch.newIntervalhas0 <= start <= end <= 150.
Run checks your code against the 3 examples. Submit checks it against all 223 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.