Definition
- Insert Interval – insert a new interval into a sorted non-overlapping list and merge any overlaps to keep the list sorted and non-overlapping.
- Three phases – (1) copy intervals ending before the new one starts, (2) merge all intervals overlapping the new one into one expanded interval, (3) copy remaining intervals.
- Merge rule – take
min(newStart, existingStart)andmax(newEnd, existingEnd)for each overlap. - Pre-sorted – the input is already sorted, so no sort step is needed, keeping the solution at O(n).
- Space – O(n) for the result list; the input is not mutated.
At the National Bank of India, Rajesh maintains a sorted, non-overlapping schedule of periods when an account is on hold. When a new fraud investigation triggers another hold period, he walks the list once: he keeps every hold that finishes before the new one starts untouched, he fuses the new hold with every hold it bumps into to form one bigger hold, and then he keeps the rest of the holds that begin after the fused hold ends.
Understanding the Concepts
What is the Insert Interval problem?
You are given a list of non-overlapping intervals sorted by their start time, and a new interval to insert. You must produce a new list that is still sorted and non-overlapping, merging the new interval with any existing intervals it overlaps.
This is LeetCode 57 and is a classic merge-intervals pattern problem.
package com.bank.service;
// Existing holds (sorted, non-overlapping): [[1,3], [6,9]]
// New hold: [2,5]
// After insert: [[1,5], [6,9]] (new hold merged with [1,3])
How does the three-phase approach work?
Because the input is already sorted and non-overlapping, you solve it in a single linear pass with three phases.
Phase 1 (Before): Copy every interval that ends strictly before the new interval starts. These lie entirely to the left and cannot overlap.
Phase 2 (Merge): For every remaining interval whose start is at or before the new interval's end, it overlaps. Merge it into the new interval by taking min(starts) and max(ends). Continue until no more overlaps. Then add the merged interval.
Phase 3 (After): Copy all remaining intervals. They start after the merged interval ends and cannot overlap.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class InsertInterval {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0;
int n = intervals.length;
// Phase 1: intervals that end before newInterval starts
while (i < n && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
// Phase 2: merge overlapping intervals
int mergedStart = newInterval[0];
int mergedEnd = newInterval[1];
while (i < n && intervals[i][0] <= mergedEnd) {
mergedStart = Math.min(mergedStart, intervals[i][0]);
mergedEnd = Math.max(mergedEnd, intervals[i][1]);
i++;
}
result.add(new int[]{mergedStart, mergedEnd});
// Phase 3: remaining intervals after the merged one
while (i < n) {
result.add(intervals[i]);
i++;
}
return result.toArray(new int[result.size()][]);
}
}
Why does the merge phase take the minimum of starts?
The merge must take min(newStart, existingStart) not just max(ends). The new interval might begin before some existing interval it overlaps. For example, inserting [2,5] into [[3,6]] should produce [[2,6]], not [[3,6]]. The minimum-of-starts rule ensures the merged interval starts as early as the earliest overlap.
package com.bank.service;
import java.util.Arrays;
public class MinStartDemo {
public static void main(String[] args) {
InsertInterval solver = new InsertInterval();
int[][] intervals = {{3, 6}, {8, 10}};
int[] newInterval = {2, 5};
int[][] result = solver.insert(intervals, newInterval);
// [2,5] overlaps [3,6] -> merged = [min(2,3), max(5,6)] = [2,6]
for (int[] r : result) {
System.out.println(Arrays.toString(r));
}
}
}
[2, 6]
[8, 10]
What if the new interval swallows multiple existing intervals?
The merge phase loops as long as the current interval's start is at or before the merged end. This means one new interval can absorb several existing ones.
package com.bank.service;
import java.util.Arrays;
public class MultiMergeDemo {
public static void main(String[] args) {
InsertInterval solver = new InsertInterval();
// Existing: [1,2], [3,5], [6,7], [8,10], [12,16]
// New: [4,8] overlaps [3,5], [6,7], [8,10]
int[][] intervals = {{1,2},{3,5},{6,7},{8,10},{12,16}};
int[] newInterval = {4, 8};
int[][] result = solver.insert(intervals, newInterval);
for (int[] r : result) {
System.out.print(Arrays.toString(r) + " ");
}
}
}
[1, 2] [3, 10] [12, 16]
What are the edge cases?
- **New interval before all existing**: `[[3,5]]` + `[1,2]` -> `[[1,2],[3,5]]`. Phase 1 copies nothing, phase 2 finds no overlap, phase 3 copies `[3,5]`. - **New interval after all existing**: `[[1,2]]` + `[5,7]` -> `[[1,2],[5,7]]`. Phase 1 copies `[1,2]`, phase 2 finds no overlap. - **New interval contains all existing**: `[[2,3],[5,6]]` + `[1,10]` -> `[[1,10]]`. Phase 2 absorbs everything. - **Empty existing list**: just return the new interval. - **Adjacent intervals**: `[[1,2]]` + `[3,5]` -> no overlap (2 < 3), so `[[1,2],[3,5]]`.
package com.bank.service;
import java.util.Arrays;
public class EdgeCaseDemo {
public static void main(String[] args) {
InsertInterval solver = new InsertInterval();
// New before all
print(solver.insert(new int[][]{{3,5}}, new int[]{1,2}));
// Empty existing
print(solver.insert(new int[][]{}, new int[]{5,7}));
// New contains all
print(solver.insert(new int[][]{{2,3},{5,6}}, new int[]{1,10}));
}
private static void print(int[][] result) {
for (int[] r : result) System.out.print(Arrays.toString(r) + " ");
System.out.println();
}
}
[1, 2] [3, 5]
[5, 7]
[1, 10]
What are common mistakes?
The two most common bugs:
1. Forgetting min-of-starts: only updating the end but not the start of the merged interval. This produces wrong results when the new interval starts before an overlapping existing one.
// WRONG: only tracking max of ends
mergedEnd = Math.max(mergedEnd, intervals[i][1]);
// Missing: mergedStart = Math.min(mergedStart, intervals[i][0]);
2. Re-sorting the input: a candidate who sorts the combined list has missed the pre-sorted precondition. The whole value of this problem is doing it in O(n) without sorting.
What about the banking domain use case?
At the National Bank of India, the account-hold system maintains a sorted, non-overlapping schedule of periods when an account is on hold for fraud investigation. When a new hold is requested, it is inserted and merged with any existing overlapping holds so the schedule stays clean.
package com.bank.service;
import java.util.Arrays;
public class AccountHoldScheduler {
public static void main(String[] args) {
// Existing holds: day 1-3, day 6-9, day 12-15
int[][] holds = {{1,3}, {6,9}, {12,15}};
// New fraud investigation hold: day 5-10
int[] newHold = {5, 10};
InsertInterval scheduler = new InsertInterval();
int[][] updated = scheduler.insert(holds, newHold);
System.out.println("Updated hold schedule:");
for (int[] h : updated) {
System.out.println(" Day " + h[0] + " to Day " + h[1]);
}
}
}
Updated hold schedule:
Day 1 to Day 3
Day 5 to Day 10
Day 12 to Day 15
What should a senior engineer know?
- The three-phase structure is the standard clean solution. It exploits the pre-sorted precondition.
- This builds on the merge-intervals pattern (LeetCode 56) but with the sort step already done.
- The result is a fresh list; the input is not mutated, which is safer in a multi-threaded environment.
- For frequent insertions into a large schedule, consider an interval tree for O(log n) per operation instead of O(n).
What are common interview follow-up questions?
- What is the time complexity? (O(n) because the input is pre-sorted.)
- Why not re-sort? (The input is already sorted. Sorting would be O(n log n), which is worse.)
- What if intervals touch but do not overlap? (
[1,2]and[3,5]do not overlap because 2 < 3.) - How would you handle this with an interval tree? (Insert in O(log n) and query overlaps in O(log n + k) where k is the number of overlaps.)
Visual Overview
Insert Interval: Three-Phase Linear Pass
Existing: [1,3] [6,9] [12,15]
New: [5,10]
Phase 1 (Before): [1,3] ends at 3 < 5 → copy
Phase 2 (Merge): [6,9] starts at 6 <= 10 → overlap
merged = [min(5,6), max(10,9)] = [5,10]
[12,15] starts at 12 > 10 → no overlap
→ add [5,10]
Phase 3 (After): [12,15] → copy
Result: [1,3] [5,10] [12,15]
┌─────┐ ┌──────────┐ ┌──────────┐
│ 1─3 │ │ 5──10 │ │ 12──15 │
└─────┘ └──────────┘ └──────────┘
Key Takeaway
The Insert Interval problem gives you an already sorted list of non-overlapping intervals and a new interval, and asks for the sorted non-overlapping list after inserting and merging. Because the input is already sorted, you solve it in a single O(n) pass rather than re-sorting, using three clearly separated phases.
In the first phase you copy every existing interval that ends before the new interval starts, since those lie entirely to the left and cannot overlap. In the second phase you merge every interval whose start is at or before the new interval's end, folding each into the new interval by taking the minimum of the starts and the maximum of the ends. In the third phase you copy the remaining intervals, which all start after the merged interval and cannot overlap.
The details to emphasize are that the merge phase takes the minimum of the starts, not just the maximum of the ends, because the new interval may begin before some overlapping existing interval, and that the merge continues consuming intervals as long as they overlap, because one new interval can swallow several existing ones.
At the National Bank of India, the account-hold system maintained a sorted non-overlapping schedule of hold periods, and whenever a new fraud investigation triggered another hold, the three-phase insert-and-merge kept the schedule clean in a single linear pass.
Remember one sentence: three phases in one linear pass, copy-before, merge-overlaps-with-min-start-and-max-end, copy-after.
---