Insert Interval
Problem Statement
You are given a list of non-overlapping intervals sorted by start time and a new interval. Insert the new interval into the list so that the result remains sorted and non-overlapping, merging intervals when necessary.
Input
A sorted, non-overlapping matrix intervals and one interval newInterval = [start, end].
Output
A sorted, non-overlapping matrix after inserting and merging newInterval.
Constraints
- •
0 <= intervals.length <= 10^4 - •
intervals[i].length == 2 - •
intervals is sorted by start and contains no overlapping intervals - •
newInterval.length == 2 - •
0 <= start <= end <= 10^5
Examples
Example 1
intervals = [[1,3],[6,9]], newInterval = [2,5]
[[1,5],[6,9]]Example 2
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
[[1,2],[3,10],[12,16]]Example 3
intervals = [], newInterval = [5,7]
[[5,7]]Learning Objectives
- Use sorted, non-overlapping input to avoid sorting again.
- Partition the sweep into intervals before, overlapping with, and after the inserted interval.
- Maintain the growing inserted interval as a current merged block.
- Handle empty input and endpoint-touching overlaps cleanly.
Intuition
The greedy insight is that the existing list is already sorted and clean. The new interval can only affect one contiguous region: intervals before it are safely copied, intervals that overlap it are absorbed into one growing interval, and intervals after it are safely copied.
The tempting wrong idea is to append the new interval, sort everything, and run Merge Intervals. That is correct but ignores the stronger input guarantee. A single sweep can preserve order and merge only the one region touched by the new interval.
Common mistakes
- ×Sorting again even though the input is already sorted.
- ×Using **intervalStart < newEnd** instead of **intervalStart <= newEnd**, which misses endpoint-touching overlap.
- ×Appending the merged new interval too early before all overlapping intervals have been absorbed.
- ×Forgetting to copy the trailing intervals after the merge phase finishes.
Algorithm Explanation
Greedy strategy
Sweep the sorted intervals once. Copy every interval that ends before the new interval starts. Then greedily absorb every interval whose start is at or before the current new interval end. Once an interval starts after the merged new interval, the merge region is complete, so append the merged interval and copy the rest.
Why it works
Because the original intervals are sorted and non-overlapping, intervals before the new interval cannot be affected by later intervals. All intervals that overlap the inserted interval appear consecutively. After the first interval that starts beyond the current merged end, no later interval can overlap the merged interval either.
Proof of correctness
Consider any valid output after inserting newInterval. Every original interval ending before the new interval starts is disjoint from the inserted coverage, so exchanging any different placement for copying it unchanged preserves sorted order and coverage. For the overlapping region, all intervals connected to the new interval must be represented by one interval whose start is the minimum start and whose end is the maximum end of that region; splitting it would create overlapping output intervals or duplicate coverage. The greedy sweep computes exactly those minimum and maximum boundaries by absorbing each overlapping interval. Once the next interval starts after the merged end, sorted order guarantees all later intervals are also after it, so copying the suffix unchanged is forced. Therefore the greedy output is the unique sorted non-overlapping representation of the inserted coverage.
Algorithm
- Create an empty result list and start at index 0.
- Append all intervals with end < newStart.
- While intervals overlap the current new interval, update start = min(start, intervalStart) and end = max(end, intervalEnd).
- Append the merged new interval once.
- Append all remaining intervals unchanged.
- Return the result as an array.
Solutions
Solution: Three-phase interval sweep
The sorted input lets us process the array in three phases: before the new interval, overlapping with it, and after it. Only the middle phase can change interval boundaries.
Step-by-step
- Copy intervals whose end is strictly before the new interval start.
- Track the current merged start and end for the inserted interval.
- Absorb every interval whose start is at or before the current merged end.
- Append the merged interval exactly once after the overlap phase.
- Copy the remaining suffix intervals unchanged.
O(n)
O(n)
The algorithm scans the input once. The output array can contain up to n + 1 intervals.
Java implementation
Dry Run
Sample input
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]. The input is already sorted by start, so trace the single sweep and current merged interval.
| step | interval in sorted order | current merged new interval | decision | output count |
|---|---|---|---|---|
| 1 | [1,2] | [4,8] | 2 < 4, so copy this interval before the merge region. | 1 |
| 2 | [3,5] | [4,8] | 3 <= 8, so merge to [3,8]. | 1 |
| 3 | [6,7] | [3,8] | 6 <= 8, so it is absorbed and the end stays 8. | 1 |
| 4 | [8,10] | [3,8] | 8 <= 8, so merge at the endpoint and extend to [3,10]. | 1 |
| 5 | [12,16] | [3,10] | 12 > 10, so append [3,10] and then copy the suffix interval. | 3 |
The output is [1,2], then the merged inserted interval [3,10], then the untouched suffix [12,16].
Interview Tips
Mention that this is Merge Intervals with a stronger precondition: the existing intervals are already sorted and non-overlapping. That is why a one-pass three-phase sweep is better than appending and sorting. Be explicit about when the merged interval is appended; appending it too early is the most common implementation bug.
Likely follow-ups
- What if you need to insert many intervals one by one?
- What if intervals are not sorted initially?
- How would you delete an interval range from the list instead of inserting one?
- How would you maintain this structure for online calendar bookings?
Similar Problems
Key Takeaways
- When intervals are already sorted, do not pay another sorting cost.
- The inserted interval can only merge with one contiguous block of intervals.
- Copy before, merge middle, copy after is the clean implementation structure.
- Append the merged interval once, after all overlaps have been consumed.