A deploy-lock service concatenates every team’s maintenance window into one list. The status page painted each row as its own red bar. After Platform booked [1, 3] and a nested drill sat inside it, the “next free slot” finder treated neighboring rows as neighboring time and invented a hole that Platform still covered. Pairwise merging until the list stopped shrinking was correct. A few thousand overlapping tickets never finished before the page timed out.

Merge Intervals asks for the disjoint union of closed ranges. An array of pairs is the input. Sorting by start is legal because the answer is occupancy, not original row ids.

This is an interview writeup, not a sweep lecture. The Merge Intervals post owns half-open vs closed encodings, why this is not Interval Scheduling, and the freeze-calendar story. Here we only care about collapsing int[][] so the output is sorted, non-overlapping, and covers exactly the same points.

The problem

Given an int[][] intervals where intervals[i] = [start_i, end_i], merge every overlapping pair and return the disjoint cover. Closed integers: [1, 4] and [4, 5] share 4 and must become [1, 5]. Order of the input does not matter. Empty input emits nothing.

intervals = [[2,5],[1,3],[8,10],[9,12]]  →  [[1,5],[8,12]]
intervals = [[3,6],[6,8]]                 →  [[3,8]]
intervals = [[5,9],[2,4]]                 →  [[2,4],[5,9]]

Note: Two closed ranges overlap when the next start is not after the current end — next[0] <= current[1]. Nested [1, 10] plus [3, 4] is the same predicate: you extend with max on the end, which here stays 10.

Pairwise merge until the list quiets

Scan every pair. If they overlap, replace them with one interval and restart. Repeat until a full pass finds nothing to swallow. Correct. Quadratic (or worse if you restart from scratch after every hit).

boolean overlaps(int[] a, int[] b) {
    return a[0] <= b[1] && b[0] <= a[1];
}

int[][] mergePairwise(int[][] intervals) {
    List<int[]> list = new ArrayList<>();
    for (int[] iv : intervals) {
        list.add(new int[] { iv[0], iv[1] });
    }
    boolean changed = true;
    while (changed) {
        changed = false;
        outer:
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (overlaps(list.get(i), list.get(j))) {
                    list.get(i)[0] = Math.min(list.get(i)[0], list.get(j)[0]);
                    list.get(i)[1] = Math.max(list.get(i)[1], list.get(j)[1]);
                    list.remove(j);
                    changed = true;
                    break outer;
                }
            }
        }
    }
    return list.toArray(new int[list.size()][]);
}

At a dozen windows this is a rounding error. At production size you paid repeated pairwise scans for a question one sort plus a linear walk answers: after a sort by start, only the next neighbor can still overlap.

Sort by start, then swallow

Sort by start. Keep one current. For each next, either extend current[1] = max(current[1], next[1]) when they overlap, or emit current and start a new one. Copy endpoints so the sweep does not mutate the caller’s row values.

sorted:  [1,3]  [2,5]  [8,10]  [9,12]

current = [1,3]
next    = [2,5]      2 <= 3    →  current = [1, max(3,5)] = [1,5]
next    = [8,10]     8 > 5     →  emit [1,5]; current = [8,10]
next    = [9,12]     9 <= 10   →  current = [8, max(10,12)] = [8,12]
flush                          →  emit [8,12]

disjoint union:  [1,5]  [8,12]

The Java is that walk:

int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][];
    }
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> out = new ArrayList<>();
    int[] current = { intervals[0][0], intervals[0][1] };
    for (int i = 1; i < intervals.length; i++) {
        int[] next = intervals[i];
        if (next[0] <= current[1]) {
            current[1] = Math.max(current[1], next[1]);
        } else {
            out.add(current);
            current = new int[] { next[0], next[1] };
        }
    }
    out.add(current);
    return out.toArray(new int[out.size()][]);
}

Time is O(n log n) from the sort, then a linear sweep. Space is O(n) for the output in the worst case (no overlaps), plus whatever the sort uses.

Note: Do not sort by end. An early-starting long range must be the occupancy you extend. Sorting by finish emits a nested short window first and fails to swallow the long tail. That fork is Interval Scheduling; this prompt keeps every occupied instant. Arrays.sort also permutes the input array; copy first if the caller still needs filing order.

What interviewers usually poke next

  • Empty or one row. Return a copy of the input. The loop never runs; you still flush current.
  • Touching vs nested vs chain. [1,4]+[4,5], [1,10]+[3,4], [1,5]+[4,8] are the same <= and the same max. Walk one of them out loud.
  • Half-open encoding. Production time is often [start, end). The predicate and the “do we merge a touch?” product rule live on the tutorial; do not mix conventions in one list.
  • Identity. Audit wants the original team windows. Merge for occupancy; keep source rows elsewhere.
  • Online inserts. A live stream should not re-sort the world. That is the next problem: Insert Interval.

You are done with this problem when you can say, out loud, why pairwise merge is correct, why sorting by start makes the neighbor check sufficient, and why max on the end swallows a nested range.