Insert Interval
The key idea
Because the intervals are already sorted by start, you can sweep once: copy every interval that ends before the new one starts, absorb every interval that overlaps by widening the new interval to cover both, then copy the rest. No re-sorting is ever needed.
Problem
You are given an array of non-overlapping intervals intervals where each intervals[i] = [start_i, end_i] represents the start and end of the i-th interval. The list is sorted in ascending order by start_i. You are also given one extra interval newInterval = [start, end].
Insert newInterval into intervals so that the array stays sorted by start and still contains no overlapping intervals, merging any intervals that overlap with the inserted one. Return the resulting array of intervals. You do not need to modify intervals in place; you may build and return a new list.
Constraints
0 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^5intervalsis sorted bystart_iin ascending ordernewInterval.length == 20 <= start <= end <= 10^5
Examples
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Intervals problems
- Meeting RoomsEASY
- Merge IntervalsMEDIUM
- Non-overlapping IntervalsMEDIUM