Merge Intervals

The problem, simply

You get a list of time ranges. Each range is a pair [start, end]. Some ranges overlap, and some only touch at one end, like [1, 4] and [4, 5]. Join every bunch of ranges that overlap or touch into one range.

Give back the joined ranges. None of them may overlap each other. Together they must cover exactly the same times as the input.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep a list of finished groups. Take the ranges one at a time. Compare the new range with every group. Each group it overlaps gets swallowed: the new range grows to cover it and the group is removed. Then the grown range goes into the list.

1. For each range, set start and end from it.
2. Walk every group in the list. If the group overlaps [start, end], grow start and end to cover it, and remove the group.
3. Add [start, end] to the list.

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> groups = new ArrayList<>();
        for (int[] in : intervals) {
            int start = in[0], end = in[1];
            Iterator<int[]> it = groups.iterator();
            while (it.hasNext()) {
                int[] g = it.next();
                if (g[0] <= end && start <= g[1]) {    // they overlap or touch
                    start = Math.min(start, g[0]);
                    end = Math.max(end, g[1]);
                    it.remove();                       // swallow that group
                }
            }
            groups.add(new int[] { start, end });
        }
        return groups.toArray(new int[0][]);
    }
}

How long it takes: each new range is compared with every group so far, O(n^2). Extra room: the list of groups, O(n). Why does one walk over the groups catch everything? A range that grows can only reach a group that touches something it already swallowed, and the groups never touch each other.

Way 2: the clever way

Sort first, then one walk is enough.

1. Sort the ranges by start time.
2. Put the first range in the answer. It is the current block.
3. For each next range: if its start is at most the current block's end, they overlap. Stretch the block's end to max(block end, range end).
4. Otherwise the block is finished. Add this range to the answer as the new current block.

After sorting, a range can only overlap the block right before it. Any earlier block already ended before that block started. The thin line in the picture marks where the current block ends.

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return new int[0][];
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));   // by start time
        List<int[]> out = new ArrayList<>();
        int[] block = intervals[0].clone();
        out.add(block);
        for (int i = 1; i < intervals.length; i++) {
            int[] in = intervals[i];
            if (in[0] <= block[1]) {
                block[1] = Math.max(block[1], in[1]);   // overlaps: stretch the block
            } else {
                block = in.clone();                     // a gap: start a new block
                out.add(block);
            }
        }
        return out.toArray(new int[0][]);
    }
}

How long it takes: sorting is O(n log n) and the walk is O(n), so O(n log n) in total. Extra room: the answer list, O(n), plus whatever the sort uses.

Watch out for

• Use <= for the overlap test if touching ranges should join. Ask the interviewer; some versions treat [1, 4] and [4, 5] as separate.
• Sort with Integer.compare(a[0], b[0]), not a[0] - b[0]. Subtraction can overflow for very large or very negative values.
• Forgetting the empty input. Return an empty array before reading intervals[0].

What interviewers ask next

• Insert one new range into a sorted list of non-overlapping ranges. Copy the ranges that end before it, join every range that overlaps it, then copy the rest. That is O(n) with no sort.
• How many meeting rooms are needed? Sort the starts and the ends separately and sweep, or use a min heap of end times. The most meetings running at once is the answer.
• Remove the fewest ranges so none overlap. Sort by end time and greedily keep each range that starts after the last kept one ends.
• What if the ranges arrive one by one in a stream? Keep them in a sorted map (a TreeMap keyed by start) and join with the neighbours on each insert.

Remember this

Grown-up words: the sticky notes are intervals, joining them is merging overlapping intervals, the current block is the last interval in the output, and walking once after sorting is a sweep line.