Merge Overlapping Intervals

The problem, simply

You get a list of intervals. Each one is [start, end], like a meeting that starts at start and ends at end. The list can be in any order.

Join every pair that overlaps, and keep joining until nothing overlaps any more. Give back the joined intervals, sorted by start. Two intervals that only touch, like [1,4] and [4,5], also count as overlapping.

A story to remember it

Picture it

Examples

Way 1: the simple way

Grow groups by hand, without sorting.

1. Take the first interval that is not used yet. It starts a group.
2. Scan all unused intervals. Any that overlaps the group joins it, and the group stretches to cover it.
3. Repeat the scan until a full pass adds nobody. Then the group is finished.
4. Start the next group with the next unused interval. At the end, sort the groups by start.

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        boolean[] used = new boolean[n];
        List<int[]> out = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true;
            int lo = intervals[i][0], hi = intervals[i][1];   // the group
            boolean grew = true;
            while (grew) {                                    // scan again until nobody joins
                grew = false;
                for (int j = 0; j < n; j++) {
                    if (!used[j] && intervals[j][0] <= hi && lo <= intervals[j][1]) {
                        lo = Math.min(lo, intervals[j][0]);
                        hi = Math.max(hi, intervals[j][1]);
                        used[j] = true;
                        grew = true;
                    }
                }
            }
            out.add(new int[]{lo, hi});
        }
        out.sort((a, b) -> Integer.compare(a[0], b[0]));
        return out.toArray(new int[0][]);
    }
}

How long it takes: every scan is O(n), and each extra scan only happens when someone joined, so there are at most about 2n scans in total. That is O(n^2). Extra room: the used marks and the answer, O(n).

Way 2: the clever way

Sort by start time first. After that, a new interval can only overlap the most recent block, because every older block ended before that one started. So keep the blocks on a stack and only ever look at the top.

1. Sort the intervals by start.
2. For each interval: if the stack is empty, or the interval starts after the top block ends, push it as a new block.
3. Otherwise they overlap. Stretch the top block's end to the bigger of the two ends.
4. The stack, from bottom to top, is the answer.

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] a = intervals.clone();
        Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));   // sort by start
        Deque<int[]> stack = new ArrayDeque<>();
        for (int[] iv : a) {
            if (stack.isEmpty() || iv[0] > stack.peek()[1]) {
                stack.push(new int[]{iv[0], iv[1]});             // a gap: new block
            } else {
                int[] top = stack.peek();
                top[1] = Math.max(top[1], iv[1]);                // overlap: stretch the top
            }
        }
        int[][] out = new int[stack.size()][];
        for (int i = out.length - 1; i >= 0; i--) out[i] = stack.pop();   // top is the last block
        return out;
    }
}

How long it takes: sorting costs O(n log n), and the walk is O(n), so O(n log n) in total. Extra room: the stack can hold n blocks when nothing overlaps, O(n). A plain list where you only touch the last block works exactly the same way and is what most people write.

Watch out for

• Using iv[0] >= top[1] for the gap test. Then touching intervals like [1,4] and [4,5] stay apart. The gap test is iv[0] > top[1].
• Sorting with (x, y) -> x[0] - y[0]. With very large or very negative numbers the subtraction overflows. Integer.compare is safe.
• Changing the input arrays by accident. Push copies so the caller's data stays the same.

What interviewers ask next

• Insert one new interval into an already sorted, non overlapping list. No sort needed: copy the ones that end before it, merge the ones that overlap it, copy the rest. O(n).
• Minimum number of meeting rooms. Sort the starts and the ends separately and sweep with two pointers, or use a min heap of end times. The answer is the most meetings happening at once.
• Total time covered by all intervals. Merge them, then add up end - start for each block.
• Intervals arrive one by one as a stream. Keep them in a sorted tree map keyed by start, and merge with the neighbors on each insert, O(log n) per insert.
• Remove the fewest intervals so none overlap. Sort by end and keep greedily the one that ends first. This is the activity selection idea.

Remember this

Grown-up words: the sticky notes are intervals, joining them is merging, the pile of blocks is a stack (or the last element of a result list), and sorting first so that one simple choice per step is enough is a greedy algorithm.