56. Merge Intervals

Merge Intervals is the problem that teaches the move behind almost every interval question: sort by start, then sweep left to right. Get that reflex and interval problems stop looking like puzzles and start looking like one template with different endings.

The problem

You’re handed a list of intervals like [start, end], and some of them overlap. Collapse every overlapping group into a single interval and return what’s left. (Full statement on LeetCode.)

Say the input is [[1,3], [2,6], [8,10]]. The first two share the range from 2 to 3, so they fuse into [1,6]; [8,10] sits alone. The answer is [[1,6], [8,10]].

Intuition: sorting turns overlap into a one-step check

Unsorted, “does this interval overlap any other?” is a question about the whole list — every interval could touch any other. That’s the trap. Sort by start value and the question shrinks to a comparison with a single neighbor.

Here’s why. Once intervals are ordered by start, walk them in that order and keep the last merged interval as [curStart, curEnd]. The next interval’s start is always $\ge curStart$, so the only way they don’t overlap is if it begins strictly after curEnd:

$\text{next.start} > curEnd \;\Rightarrow\; \text{disjoint}$

If that’s false, they overlap (or just touch, which counts here), and merging is trivial: the start stays put, and the end stretches to $\max(curEnd, \text{next.end})$. The max matters — a later interval like [2,6] swallowed inside a wider one like [1,8] shouldn’t shrink the end back to 6. So one sort plus one linear pass does it; the sort is the whole cost.

Solution

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        // Order by start so each interval only needs to look at the previous one.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> merged = new ArrayList<>();
        for (int[] cur : intervals) {
            int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);

            // Gap? cur starts strictly after last ends -> it's a fresh interval.
            if (last == null || cur[0] > last[1]) {
                merged.add(new int[] { cur[0], cur[1] });
            } else {
                // Overlap or touch: keep the start, extend the end as far as needed.
                last[1] = Math.max(last[1], cur[1]);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

A note on the comparator: Integer.compare(a[0], b[0]) instead of a[0] - b[0]. Subtraction can overflow when starts span the full int range, silently flipping the sort order. It doesn’t bite on LeetCode’s non-negative bounds, but it’s the kind of habit worth carrying into real code.

Complexity

	Time	Space
Sort + sweep	$O(n \log n)$	$O(n)$

The sort dominates the runtime; the sweep itself is $O(n)$. Space is $O(n)$: the output list holds up to $n$ intervals, and even setting the result aside, sorting an int[][] (an object array) with a comparator runs TimSort, which allocates $O(n)$ temporary references — so it’s never truly in-place $O(\log n)$ here.

In an interview

Say the plan before you write it: “sort by start, then one pass — extend the last interval when it overlaps, otherwise start a new one.” That single sentence signals you know the pattern rather than reinventing it live.

The edge case interviewers probe is touching intervals: do [1,4] and [4,5] merge? Here they do, which is why the gap test is cur[0] > last[1] (strict) and not >=. Flip that one operator and adjacent intervals wrongly stay split — worth stating your assumption out loud so you’re aligned before coding.

This sort-then-sweep skeleton is the backbone of the whole interval patterns family. Once merging clicks, Insert Interval is the same idea when the list is already sorted and you drop in one new interval, and Non-overlapping Intervals flips it into a greedy “how many to remove” count.

References

• LeetCode 56 — Merge Intervals