Insert Interval
MediumIntervals
You are given a list of closed intervals intervals, where intervals[i] = [start, end]. The list is sorted by start and no two intervals overlap.
You are also given one more interval, new_interval = [start, end]. Insert it into intervals so that the list stays sorted by start and still has no overlapping intervals, merging wherever necessary.
Intervals include both endpoints, so two intervals that share even a single point (like [1, 3] and [3, 5]) overlap and must be merged into one ([1, 5]).
Return the resulting list. You may build a new list instead of modifying intervals in place.
Example 1
- Input:
- intervals = [[1, 2], [4, 6], [8, 10], [13, 15]], new_interval = [5, 9]
- Output:
- [[1, 2], [4, 10], [13, 15]]
- Explanation
[5, 9]overlaps[4, 6]and[8, 10], so the three merge into[4, 10].[1, 2]ends before 5 and[13, 15]starts after 9, so they stay as they are.
Example 2
- Input:
- intervals = [[1, 3], [6, 8]], new_interval = [3, 6]
- Output:
- [[1, 8]]
- Explanation
- Intervals are inclusive, so
[3, 6]shares the point 3 with[1, 3]and the point 6 with[6, 8]. Everything merges into[1, 8].
Example 3
- Input:
- intervals = [], new_interval = [4, 8]
- Output:
- [[4, 8]]
- Explanation
- There is nothing to merge with, so the result is just the new interval.
Constraints
0 <= intervals.length <= 10^4intervals[i].length == 20 <= start <= end <= 10^5intervalsis sorted bystartand non-overlappingnew_interval.length == 2