Insert Interval
Problem
intervals is a list of non-overlapping intervals sorted by start.
Add newInterval to it and return a list that is still sorted and
non-overlapping, merging newInterval with every interval it overlaps
(touching endpoints count as overlap).[[1,3],[6,9]], new=[2,5]Output[[1,5],[6,9]][[1,2],[3,5],[6,7]], new=[4,6]Output[[1,2],[3,7]][], new=[5,7]Output[[5,7]]0 ≤ n ≤ 104 · intervals sorted by start, disjoint · 0 ≤ start ≤ end ≤ 105
Try it yourself
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
}
}
Instinct See [start, end] pairs, meetings, bookings or the word "overlap"? Sort by an endpoint, then sweep left to right carrying one running fact.
Memory hack Sort, then sweep - start time to merge, end time to choose, +1/-1 events to count the crowd.
Open the Intervals & Line Sweep guide →Approaches
Brute ForceAppend, Sort, Merge
O(n log n)Space O(n)Ignore the sorted guarantee: add newInterval to the list, sort by
start, and run the standard Merge Intervals sweep. Correct for any input, but
re-sorts data that is already sorted.
public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> all = new ArrayList<>(Arrays.asList(intervals)); all.add(newInterval); all.sort((a, b) -> Integer.compare(a[0], b[0])); List<int[]> merged = new ArrayList<>(); for (int[] in : all) { if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < in[0]) { merged.add(new int[] {in[0], in[1]}); } else { int[] last = merged.get(merged.size() - 1); last[1] = Math.max(last[1], in[1]); } } return merged.toArray(new int[0][]); }
Reuses a known routine; wastes the sorted-input guarantee.
OptimalThree-Phase Linear Sweep
O(n)Space O(n) outputPhase 1: copy intervals that end before new.start. Phase 2: while
an interval starts ≤ new.end, it overlaps — grow
[start, end] with min/max. Add the merged interval. Phase 3: copy the
rest. Sortedness guarantees nothing in phase 3 can overlap.
public int[][] insert(int[][] intervals, int[] newInterval) { List<int[]> result = new ArrayList<>(); int i = 0, n = intervals.length; int start = newInterval[0], end = newInterval[1]; while (i < n && intervals[i][1] < start) result.add(intervals[i++]); // before while (i < n && intervals[i][0] <= end) { // overlap start = Math.min(start, intervals[i][0]); end = Math.max(end, intervals[i][1]); i++; } result.add(new int[] {start, end}); while (i < n) result.add(intervals[i++]); // after return result.toArray(new int[0][]); }
Dry run[[1,2],[3,5],[6,7],[8,10],[12,16]], new=[4,8]
- i=01-2i3-56-78-1012-162 < 4 → copy
- i=11-23-5i6-78-1012-163 ≤ 8 → [3,8]
- i=21-23-56-7i8-1012-166 ≤ 8 → [3,8]
- i=31-23-56-78-10i12-168 ≤ 8 → [3,10]
- i=41-23-10··12-16iadd [3,10]; copy rest ✔
Single pass, uses the sorted input; the O(n) output copy is unavoidable.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Append, Sort, Merge | O(n log n) | O(n) |
| Optimal | Three-Phase Linear Sweep | O(n) | O(n) output |
- Forgetting the new interval when it goes at the very end or the list is empty.
- Using
<in the overlap test — [1,5] and new [5,7] must merge. - Mutating the caller's
newIntervalarray in place — copy into locals.
- Point out the given sortedness — it's why O(n) is possible.
- Describe the three phases before coding; each is a simple while loop.
- Test: empty list, insert at front, at back, and swallowing everything.