54. Insert Interval

Add the new interval to the list, sort everything, then merge overlapping intervals just like the Merge Intervals problem.

Brute Force

Append newInterval to the end of intervals, sort the combined list by start time, then sweep through and merge any overlapping pairs.

Sorting costs O(n log n) even though the input was already sorted. Space is O(n) for the output.

Why it is slow: We throw away the fact that intervals is already sorted and re-sort the entire list.

import java.util.*;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> all = new ArrayList<>(Arrays.asList(intervals));
        all.add(newInterval);
        all.sort((a, b) -> a[0] - b[0]);
        List<int[]> merged = new ArrayList<>();
        merged.add(all.get(0));
        for (int i = 1; i < all.size(); i++) {
            int[] last = merged.get(merged.size() - 1);
            if (all.get(i)[0] <= last[1]) {
                last[1] = Math.max(last[1], all.get(i)[1]);
            } else {
                merged.add(all.get(i));
            }
        }
        return merged.toArray(new int[0][]);
    }
}

Since the intervals are already sorted, sweep left to right: collect intervals entirely before the new one, merge all that overlap with it, then collect the rest.

Mental Model

Picture the sorted intervals on a number line. The new interval lands somewhere in the middle. Everything to its left (ending before it starts) is untouched. Everything to its right (starting after it ends) is also untouched. Only the intervals in between need merging with it.

Algorithm Steps

1. Create an empty result list.
2. Phase 1 (Before): Walk through intervals. While the current interval ends before newInterval starts (intervals[i][1] < newInterval[0]), add it to the result unchanged.
3. Phase 2 (Overlap): While the current interval starts before or at newInterval's end (intervals[i][0] <= newInterval[1]), merge by expanding: newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])].
4. Add the (possibly expanded) newInterval to the result.
5. Phase 3 (After): Append all remaining intervals to the result.

Worked Walk-through

intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Edge Cases

• Empty intervals list: Just return [newInterval].
• New interval before all others: Phase 1 collects nothing, Phase 2 collects nothing, result is [newInterval] + intervals.
• New interval after all others: Phase 1 collects everything, newInterval is appended at the end.

Complexity

• Time: O(n) — single pass through the intervals.
• Space: O(n) — the result list holds at most n+1 intervals.