On-call already stores coverage as a sorted, disjoint list of windows. A new override arrives: one extra [start, end] that may sit in a gap, overlap one block, or swallow several. Last quarter the same service collapsed an unsorted dump of team freezes — that is Merge Intervals, and a sort-then-sweep was the right bill. This quarter the cover is already honest. The intern appended the override and called merge from scratch. A few dozen rows were fine. Re-sorting the whole roster on every override was still the wrong invariant to throw away.

Insert Interval splices one new range into a sorted disjoint cover. An array of pairs is the input. The sort is already done; the walk is linear.

This is an interview writeup, not a merge lecture. The Merge Intervals post owns the sweep and the encoding. Here we only care about using the invariant you were given: copy everything entirely before the new range, grow the overlap, copy the rest.

The problem

Given a sorted, non-overlapping int[][] intervals and a new int[] newInterval, insert the new range and merge as needed. Return the updated disjoint cover, still ordered by start. Closed integers: a shared endpoint is overlap. The new range may land wholly to the left, wholly to the right, inside a gap, or overlap one or more existing rows.

intervals = [[1,4],[8,11]],  newInterval = [3,6]   →  [[1,6],[8,11]]
intervals = [[2,3],[5,7],[9,10],[12,14]],
             newInterval = [6,13]                   →  [[2,3],[5,14]]
intervals = [],              newInterval = [4,6]   →  [[4,6]]

Note: “Entirely before” means the existing row’s end is strictly left of the new start (intervals[i][1] < newInterval[0]). Overlap starts when that fails and continues while intervals[i][0] <= newInterval[1].

Append, then merge from scratch

Push newInterval onto the list and run the full sort-by-start sweep. Correct. It throws away the fact that intervals was already a disjoint cover.

int[][] insertByRemerge(int[][] intervals, int[] newInterval) {
    int[][] all = Arrays.copyOf(intervals, intervals.length + 1);
    all[intervals.length] = new int[] { newInterval[0], newInterval[1] };
    return merge(all);   // sort + sweep from Merge Intervals
}

At a dozen windows this is a rounding error. At production size you paid O(n log n) for a question the given order already answers in one pass: copy the left, merge the middle, copy the right.

One pass: copy left, merge, copy right

Walk i from 0 to n-1 once.

  1. While intervals[i] ends before the new start, copy it as-is.
  2. While intervals[i] overlaps the new range, fold it in: start = min, end = max.
  3. Emit the (possibly grown) new range, then copy whatever remains.
intervals = [2,3]  [5,7]  [9,10]  [12,14]     newInterval = [6,13]

i=0  [2,3]    end 3 < 6              copy left [2,3]
i=1  [5,7]    end 7 is not < 6       stop copy-left
i=1  [5,7]    start 5 <= 13          merge → [5,13]
i=2  [9,10]   start 9 <= 13          merge → [5,13]
i=3  [12,14]  start 12 <= 13         merge → [5,14]
emit [5,14]
nothing remaining

result:  [2,3]  [5,14]

The new range ate [5, 7], [9, 10], and [12, 14] in one merge loop, and left [2, 3] untouched. No sort. No second pass.

The Java is that walk. Copy endpoints so the splice does not mutate the caller’s arrays.

int[][] insert(int[][] intervals, int[] newInterval) {
    List<int[]> out = new ArrayList<>();
    int i = 0;
    int n = intervals.length;
    int ns = newInterval[0];
    int ne = newInterval[1];

    while (i < n && intervals[i][1] < ns) {
        out.add(new int[] { intervals[i][0], intervals[i][1] });
        i++;
    }
    while (i < n && intervals[i][0] <= ne) {
        ns = Math.min(ns, intervals[i][0]);
        ne = Math.max(ne, intervals[i][1]);
        i++;
    }
    out.add(new int[] { ns, ne });
    while (i < n) {
        out.add(new int[] { intervals[i][0], intervals[i][1] });
        i++;
    }
    return out.toArray(new int[out.size()][]);
}

Time is O(n) — one pass, no re-sort. Space is O(n) for the output. The append-then-merge brute is the same output with an extra O(n log n) sort you did not need.

Note: Do not binary-search then skip the merge loop. A lower bound on start finds the first overlap candidate, but several later rows can still fold into the new range. The linear scan already visits each of those once; a binary search does not remove the merge loop.

What interviewers usually poke next

  • New range wholly left or wholly right. The first loop copies nothing (or everything). The merge loop never runs. You still emit newInterval in the middle of the three stages.
  • New range swallows the whole cover. [[1,2],[3,5]] plus [0, 10] becomes [[0, 10]]. The merge loop eats every row.
  • Gap insert, no overlap. [[1,2],[5,6]] plus [3, 4] copies left, merge loop skips, emits [3, 4], copies right.
  • Empty intervals. Both while-copy loops no-op; the result is a one-row cover.
  • A stream of inserts. Repeated linear splices are O(n) each. If overrides arrive continuously, say you want a tree of starts, not this one-shot pass. The tutorial names that fork; do not build it at the board unless they ask.

You are done with this problem when you can say, out loud, why append-plus-merge is correct, why the given sorted disjoint cover makes a full re-sort waste, and where the three stages of the linear splice start and stop.