Insert Interval
Medium · Intervals · Array · Intervals
Problem
intervals is a list of non-overlapping [start, end] pairs, already sorted by start. Insert newInterval, merging anything it touches, and return the result still sorted and non-overlapping.
Examples
Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]]
[2,5] overlaps [1,3], so they merge.
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]]
[4,8] swallows three intervals at once.
Constraints
- 0 <= len(intervals) <= 10^4
- intervals is sorted by start and non-overlapping
- 0 <= start <= end <= 10^5
Approaches
- Append and re-merge — time O(n log n), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
