Insert Interval — Merge While Inserting
Walk the sorted intervals, append those ending before the new interval, merge overlaps, then append the rest.
Problem Statement
Given non-overlapping intervals sorted by start and a new interval, insert it into the list while preserving order and merging overlaps.
Why This Problem Matters
- Builds on merge intervals and introduces staged iteration logic.
- Teaches how to handle immediate merging scenarios without re-sorting.
- Common in calendar apps and scheduling tasks.
Thought Process
Consume leading intervals
Push every interval that ends before the new interval starts—they can never overlap.
Merge overlaps into new interval
Expand the new interval while there is overlap; update start and end with min and max respectively.
Append trailing intervals
Once overlaps end, add the merged new interval followed by the remaining original intervals.
Step-by-Step Reasoning
- Initialise output list and index i = 0.
- Add intervals[i] to output while intervals[i][1] < newInterval[0].
- While intervals[i][0] <= newInterval[1], merge into newInterval.
- Append merged newInterval, then append remaining intervals.
Dry Run
intervals = [[1,3],[6,9]], new = [2,5]
Leading [1,3] merges to [1,5]; append [6,9] after.
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], new = [4,8]
After merging overlaps, result includes [1,2],[3,10],[12,16].
Complexity Analysis
Time
O(n)
Space
O(n)
Why
Single pass through intervals; output may hold all intervals plus the new one.
Annotated Solution
import java.util.ArrayList;
import java.util.List;
public class InsertInterval {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> output = new ArrayList<>();
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
output.add(intervals[i]);
i += 1;
}
int start = newInterval[0];
int end = newInterval[1];
while (i < intervals.length && intervals[i][0] <= end) {
start = Math.min(start, intervals[i][0]);
end = Math.max(end, intervals[i][1]);
i += 1;
}
output.add(new int[]{start, end});
while (i < intervals.length) {
output.add(intervals[i]);
i += 1;
}
return output.toArray(new int[output.size()][]);
}
}The algorithm runs in three phases: leading non-overlaps, merged overlaps, and trailing non-overlaps—all in a single pass.
Common Pitfalls
- Failing to append the new interval when it extends past all others.
- Using while loops without bounds checks leads to ArrayIndexOutOfBounds.
- Not updating newInterval when overlaps occur keeps stale start/end values.
Follow-Up Questions
- How would you support inserting multiple intervals efficiently?
- Can you perform the insertion in-place with O(1) extra space?