Insert Interval
Problem
Given a list of non-overlapping intervals sorted by their start time, and a new interval, insert the new interval into the list and merge all overlapping intervals, returning the updated list of intervals sorted by start time.
- 0 ≤ intervals.length ≤ 10⁴
- intervals[i].length == 2
- 0 ≤ intervals[i][0] ≤ intervals[i][1] ≤ 10⁵
- intervals is sorted by intervals[i][0]
- newInterval.length == 2
- 0 ≤ newInterval[0] ≤ newInterval[1] ≤ 10⁵
Example
intervals = [[1,3],[6,9]], newInterval = [2,5][[1,5],[6,9]]The algorithm iterates through the intervals. The first interval [1,3] overlaps with the new interval [2,5], so they are merged into [1,5]. The second interval [6,9] does not overlap and is appended as is. The final result is [[1,5],[6,9]]. The critical moment is when the algorithm detects overlap and updates the new interval boundaries to merge intervals efficiently.
Approach
Straightforward Solution
A naive approach would insert the new interval and then sort and merge all intervals, resulting in O(n log n) time due to sorting and O(n) for merging. This is inefficient given the input is already sorted and non-overlapping.
Core Observation
Intervals are sorted and non-overlapping, so the new interval can be inserted by scanning from left to right, merging overlapping intervals as they appear. Overlapping intervals share a common range where the start of one is less than or equal to the end of the other.
Path to Optimal
The key recognition signals are 'sorted intervals' and 'merge overlapping intervals'. These indicate the Merge Intervals pattern because the problem can be solved in a single linear pass by leveraging the sorted order. The algorithm scans intervals, appends those that come before the new interval, merges overlapping ones by updating boundaries, and appends the rest. This avoids sorting and reduces complexity to O(n).
Optimal Approach
Iterate through intervals once. Append all intervals that end before the new interval starts. For intervals that overlap with the new interval, merge by updating the new interval's start and end to the min and max of overlapping intervals. Once all overlaps are merged, append the merged new interval and then append the remaining intervals. This approach guarantees O(n) time and O(n) space, preserving sorted order and merging efficiently.
Time
O(n)
The algorithm performs a single pass through the list of intervals, performing constant-time operations per interval, resulting in linear time complexity.
Space
O(n)
The output list stores all intervals including the merged new interval, requiring O(n) space proportional to the input size. No additional significant auxiliary space is used.
Pattern Spotlight
Merge Intervals (Linear Scan with Boundary Updates)
When intervals are sorted and non-overlapping, insertions and merges can be done in a single pass by appending non-overlapping intervals, merging overlapping ones by updating boundaries, and then appending the rest, avoiding sorting and repeated scans.
Solution
| 1 | class Solution:
|
| 2 | def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
|
| 3 | res = []
|
| 4 |
|
| 5 | for i in range(len(intervals)):
|
| 6 | if newInterval[1] < intervals[i][0]:
|
| 7 | res.append(newInterval)
|
| 8 | return res + intervals[i:]
|
| 9 | elif newInterval[0] > intervals[i][1]:
|
| 10 | res.append(intervals[i])
|
| 11 | else:
|
| 12 | newInterval = [min(newInterval[0], intervals[i][0]),
|
| 13 | max(newInterval[1], intervals[i][1])]
|
| 14 |
|
| 15 | res.append(newInterval)
|
| 16 | return res |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public List<int[]> insert(List<int[]> intervals, int[] newInterval) { |
| 5 | List<int[]> res = new ArrayList<>(); |
| 6 | for (int i = 0; i < intervals.size(); i++) { |
| 7 | int[] interval = intervals.get(i); |
| 8 | if (newInterval[1] < interval[0]) { |
| 9 | res.add(newInterval); |
| 10 | for (int j = i; j < intervals.size(); j++) { |
| 11 | res.add(intervals.get(j)); |
| 12 | } |
| 13 | return res; |
| 14 | } else if (newInterval[0] > interval[1]) { |
| 15 | res.add(interval); |
| 16 | } else { |
| 17 | newInterval = new int[]{Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])}; |
| 18 | } |
| 19 | } |
| 20 | res.add(newInterval); |
| 21 | return res; |
| 22 | } |
| 23 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) { |
| 9 | vector<vector<int>> res; |
| 10 | for (int i = 0; i < (int)intervals.size(); i++) { |
| 11 | if (newInterval[1] < intervals[i][0]) { |
| 12 | res.push_back(newInterval); |
| 13 | for (int j = i; j < (int)intervals.size(); j++) { |
| 14 | res.push_back(intervals[j]); |
| 15 | } |
| 16 | return res; |
| 17 | } else if (newInterval[0] > intervals[i][1]) { |
| 18 | res.push_back(intervals[i]); |
| 19 | } else { |
| 20 | newInterval[0] = min(newInterval[0], intervals[i][0]); |
| 21 | newInterval[1] = max(newInterval[1], intervals[i][1]); |
| 22 | } |
| 23 | } |
| 24 | res.push_back(newInterval); |
| 25 | return res; |
| 26 | } |
| 27 | }; |
| 1 | var insert = function(intervals, newInterval) { |
| 2 | const res = []; |
| 3 | for (let i = 0; i < intervals.length; i++) { |
| 4 | if (newInterval[1] < intervals[i][0]) { |
| 5 | res.push(newInterval); |
| 6 | for (let j = i; j < intervals.length; j++) { |
| 7 | res.push(intervals[j]); |
| 8 | } |
| 9 | return res; |
| 10 | } else if (newInterval[0] > intervals[i][1]) { |
| 11 | res.push(intervals[i]); |
| 12 | } else { |
| 13 | newInterval = [Math.min(newInterval[0], intervals[i][0]), Math.max(newInterval[1], intervals[i][1])]; |
| 14 | } |
| 15 | } |
| 16 | res.push(newInterval); |
| 17 | return res; |
| 18 | }; |
Step-by-Step Solution
Accumulate Non-Overlapping Intervals Before New Interval
| 3 | res = []
|
| 5 | for i in range(len(intervals)):
|
| 9 | elif newInterval[0] > intervals[i][1]:
|
| 10 | res.append(intervals[i])
|
Objective
To append all intervals that end before the new interval starts, as they do not overlap and can be safely added to the result.
Key Insight
Since intervals are sorted and non-overlapping, any interval whose end is less than the new interval's start cannot overlap with it. Appending these intervals directly preserves order and avoids unnecessary merging. This step effectively partitions the input into intervals before the new interval and those that may overlap or come after.
Interview Quick-Check
Core Logic
Append intervals that end before the new interval starts without modification, as they are guaranteed non-overlapping.
State & Boundaries
Use the condition `newInterval[1] < intervals[i][0]` to detect when the new interval should be inserted before the current interval.
Common Pitfalls & Bugs
Failing to append these intervals before merging can lead to incorrect ordering or missed intervals.
Merge Overlapping Intervals by Expanding New Interval Boundaries
| 6 | if newInterval[1] < intervals[i][0]:
|
| 11 | else:
|
| 12 | newInterval = [min(newInterval[0], intervals[i][0]),
|
| 13 | max(newInterval[1], intervals[i][1])]
|
Objective
To merge all intervals overlapping with the new interval by updating the new interval's start and end to cover the entire overlapping range.
Key Insight
Overlapping intervals share a range where the start of one is less than or equal to the end of the other. By updating the new interval's boundaries to the minimum start and maximum end of all overlapping intervals, the algorithm effectively merges them into a single interval. This avoids multiple insertions and preserves the sorted order.
Interview Quick-Check
Core Logic
Merge overlapping intervals by updating the new interval to the min start and max end of all overlaps, ensuring a single merged interval.
State & Boundaries
Detect overlap when intervals intersect, i.e., when `newInterval[0] <= intervals[i][1]` and `newInterval[1] >= intervals[i][0]`.
Common Pitfalls & Bugs
Incorrectly merging intervals without updating boundaries can cause missed merges or incorrect intervals.
Append Merged New Interval and Remaining Intervals
| 15 | res.append(newInterval)
|
| 16 | return res |
Objective
To add the merged new interval after processing all overlaps and then append any remaining intervals that come after it.
Key Insight
After merging all overlapping intervals, the new interval represents the combined range. Appending it ensures the result contains the merged interval in the correct order. Then, appending the remaining intervals preserves the sorted order and completeness of the output.
Interview Quick-Check
Core Logic
Append the merged new interval once all overlaps are processed, then append remaining intervals to maintain sorted order.
State & Boundaries
Appending remaining intervals after the merged new interval ensures no intervals are lost or reordered.
Common Pitfalls & Bugs
Failing to append the merged new interval or remaining intervals leads to incomplete or incorrect results.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if newInterval[1] < intervals[i][0]:Check if the new interval ends before the current interval starts (no overlap).
This condition identifies the point where the new interval should be inserted before the current interval, as all subsequent intervals start after the new interval ends.
elif newInterval[0] > intervals[i][1]:Check if the new interval starts after the current interval ends (no overlap).
This condition identifies intervals that come entirely before the new interval and can be appended directly without merging.
else:Handle overlapping intervals by merging boundaries.
This else branch captures intervals that overlap with the new interval, requiring boundary updates to merge them into a single interval.
newInterval = [min(newInterval[0], intervals[i][0]),Update the new interval's start to the minimum start of overlapping intervals.
Expanding the new interval's start boundary ensures it covers all overlapping intervals from the left side, maintaining correctness.
max(newInterval[1], intervals[i][1])]Update the new interval's end to the maximum end of overlapping intervals.
Expanding the new interval's end boundary ensures it covers all overlapping intervals from the right side, completing the merge.
res.append(newInterval)Append the new interval to the result list.
Inserting the new interval here preserves sorted order and ensures it appears before all remaining intervals that start after it ends.
return res + intervals[i:]Return the result list concatenated with the remaining intervals.
Appending the remaining intervals after the new interval completes the merged list without further processing, leveraging the sorted input property.
res.append(newInterval)Append the merged new interval after processing all overlaps.
Appending the merged new interval at the end ensures it replaces all overlapping intervals as a single combined interval in the result.
res.append(intervals[i])Append the current interval to the result list.
Appending intervals that do not overlap with the new interval preserves their order and ensures correctness of the final merged list.
return resReturn the final list of merged intervals.
Returning the accumulated result completes the function, providing the correctly merged and sorted intervals including the new interval.
for i in range(len(intervals)):Iterate over each interval in the input list.
A single pass through the sorted intervals allows efficient detection of intervals before, overlapping with, or after the new interval, enabling linear-time merging.
res = []Initialize the result list to accumulate merged intervals.
This list collects all intervals in the final output, including those before, overlapping with, and after the new interval, preserving order and merged ranges.
Test Your Understanding
Why does merging overlapping intervals by updating the new interval boundaries during the scan guarantee correctness and efficiency?
Because intervals are sorted and non-overlapping, any overlap with the new interval must be contiguous. Updating the new interval boundaries to encompass all overlapping intervals ensures a single merged interval replaces them, preserving order and avoiding multiple passes or sorting.
Related Problems
Intervals pattern
Don't just read it. Drill it.
Reconstruct Insert Interval from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Insert Interval drill