Merge Intervals

MEDIUM✓ CHIP-TIMEDLC #56 — FULL STATEMENT ↗

The drill: A pile of possibly overlapping intervals arrives unsorted. Collapse every touching or overlapping group into one interval and hand back the minimal set that covers the same ground.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A collection of intervals arrives in no particular order, and some of them may overlap or touch each other. The task is collapsing every group of overlapping or touching intervals into one combined interval.

Two intervals count as needing a merge whenever they share any point in common, including the case where one interval's end lands exactly on another's start — that boundary touch still triggers a merge.

The result should be the smallest possible set of intervals that together cover exactly the same ground as the original collection, with no two of the returned intervals overlapping or touching each other.

EX 01

intervals = [[1, 4], [2, 5], [9, 11]]

→ [[1, 5], [9, 11]]

ONE MERGE, ONE STANDALONE

EX 02

intervals = [[1, 4], [4, 7]]

→ [[1, 7]]

TOUCHING AT THE EXACT BOUNDARY STILL MERGES

EX 03

intervals = [[1, 2], [5, 6], [9, 10]]

→ [[1, 2], [5, 6], [9, 10]]

ALREADY DISJOINT, NOTHING TO MERGE

intervals arrive in arbitrary order, not necessarily sorted
start values are less than or equal to their own end values
touching intervals (one's end equals another's start) count as overlapping
the returned intervals must be non-overlapping and cover the same ground

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Overlap is only easy to spot when you already know what comes next to each interval — order removes the guesswork. What single sort turns overlap checks into simple neighbor comparisons?

HINT 2 THE STRUCTURE

Sort by start. Now any interval that overlaps the one currently being built must begin before that interval's current end — nothing farther out can ever sneak back in and merge later.

HINT 3 ONE STEP FROM THE ANSWER

Sweep the sorted list keeping one 'current' interval: if the next interval's start is at or before current's end, stretch current's end; otherwise current is finished — push it and start a new one.

COACH'S BOARD — THE PATTERN, STEP BY STEP

SORT THEN SWEEPPATTERN · SORT + LINEAR MERGEintervals = [[1,4],[2,5],[9,11]]

[1,4]

[2,5]

[9,11]

STEP 1

Sorted by start: [1,4], [2,5], [9,11]. Build the merged list one interval at a time.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/merge-intervals.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ordered = sorted(intervals, key=lambda iv: iv[0])
        result = [list(ordered[0])]
        for start, end in ordered[1:]:
            if start <= result[-1][1]:
                result[-1][1] = max(result[-1][1], end)
            else:
                result.append([start, end])
        return result

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 10 LN

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        current = [list(iv) for iv in intervals]
        changed = True
        while changed:
            changed = False
            for i in range(len(current)):
                for j in range(i + 1, len(current)):
                    a, b = current[i], current[j]
                    if a[0] <= b[1] and b[0] <= a[1]:  # they overlap or touch
                        a[0] = min(a[0], b[0])
                        a[1] = max(a[1], b[1])
                        current.pop(j)
                        changed = True
                        break
                if changed:
                    break
        current.sort(key=lambda iv: iv[0])
        return current

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 19 LN

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] ordered = new int[intervals.length][];
        for (int i = 0; i < intervals.length; i++) {
            ordered[i] = new int[] { intervals[i][0], intervals[i][1] };
        }
        Arrays.sort(ordered, (a, b) -> Integer.compare(a[0], b[0]));

        List<int[]> result = new ArrayList<>();
        result.add(ordered[0]);
        for (int i = 1; i < ordered.length; i++) {
            int[] last = result.get(result.size() - 1);
            if (ordered[i][0] <= last[1]) {
                last[1] = Math.max(last[1], ordered[i][1]);
            } else {
                result.add(ordered[i]);
            }
        }
        return result.toArray(new int[0][]);
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 21 LN

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> current = new ArrayList<>();
        for (int[] iv : intervals) current.add(new int[] { iv[0], iv[1] });

        boolean changed = true;
        while (changed) {
            changed = false;
            outer:
            for (int i = 0; i < current.size(); i++) {
                for (int j = i + 1; j < current.size(); j++) {
                    int[] a = current.get(i), b = current.get(j);
                    if (a[0] <= b[1] && b[0] <= a[1]) {
                        a[0] = Math.min(a[0], b[0]);
                        a[1] = Math.max(a[1], b[1]);
                        current.remove(j);
                        changed = true;
                        break outer;
                    }
                }
            }
        }
        current.sort((a, b) -> Integer.compare(a[0], b[0]));
        return current.toArray(new int[0][]);
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 26 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED