Interval Problems

The problem

Your calendar app shows a wall of meeting blocks: 9:00–10:30, 10:00–11:00, 13:00–14:00, 10:45–12:00. You want one clean view — the stretches of the day where you're busy at all — so 9:00–10:30 and 10:00–11:00 should fuse into a single 9:00–11:00 block because they overlap. Do it by eye with four meetings; do it by hand with four hundred and you'll give up.

Underneath, an "interval" is just a pair [start, end], and the questions are always the same shape: do these overlap? merge the ones that do; how many rooms do I need at once? The blocks arrive in whatever order they were created — total chaos. And chaos is exactly the thing sorting fixes.

A first attempt

To merge overlaps, the obvious move is to compare every interval against every other, fusing any pair that overlaps and repeating until nothing changes. But overlaps chain: A overlaps B, B overlaps C, yet A and C might not touch directly. So you loop again and again until stable — an O(n²) scan (or worse) with fiddly bookkeeping about what already merged with what.

The mess comes from intervals being in random order. When a late-day meeting sits next to an early one in the list, you can never be sure you've seen everything relevant. There's no notion of "the next one to worry about."

The insight

Sort the intervals by start time. Now scan once, left to right. Because starts only ever increase, any interval that overlaps the block you're currently building must start before that block ends — and you'll meet it immediately next. There's no reaching backward. Two cases at each step:

• The next interval starts before the current block ends → they overlap, so extend the block's end to the later of the two ends.
• It starts after → there's a gap, so close the current block and start a fresh one.

Sorting turns a tangled all-pairs problem into a single clean pass. It's the intro lesson's "sort, then exploit adjacency" motif, applied to pairs.

How it works

Merging [[1,3], [2,6], [8,10], [9,11]] after sorting by start:

sorted:  [1,3] [2,6] [8,10] [9,11]

block=[1,3]
 [2,6]:  2 <= 3  overlap → block=[1,6]
 [8,10]: 8 >  6  gap     → commit [1,6], block=[8,10]
 [9,11]: 9 <= 10 overlap → block=[8,11]
end:                       commit [8,11]

result:  [1,6] [8,11]

The code

def merge_intervals(intervals):
    intervals.sort(key=lambda iv: iv[0])   # sort by start, O(n log n)
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:   # overlap
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

function mergeIntervals(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]); // sort by start
  const merged: number[][] = [];
  for (const [start, end] of intervals) {
    const last = merged[merged.length - 1];
    if (last && start <= last[1]) {
      last[1] = Math.max(last[1], end); // overlap → extend
    } else {
      merged.push([start, end]);
    }
  }
  return merged;
}

import java.util.*;

int[][] mergeIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    for (int[] iv : intervals) {
        int n = merged.size();
        if (n > 0 && iv[0] <= merged.get(n - 1)[1]) {
            merged.get(n - 1)[1] = Math.max(merged.get(n - 1)[1], iv[1]);
        } else {
            merged.add(new int[]{iv[0], iv[1]});
        }
    }
    return merged.toArray(new int[0][]);
}

#include <stdlib.h>

int cmp(const void *a, const void *b) {
    int as = (*(int (*)[2])a)[0], bs = (*(int (*)[2])b)[0];
    return (as > bs) - (as < bs);   /* by start */
}

/* intervals: n rows of {start, end}; writes merged rows, returns count */
int merge_intervals(int intervals[][2], int n, int out[][2]) {
    qsort(intervals, n, sizeof(intervals[0]), cmp);
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (k > 0 && intervals[i][0] <= out[k - 1][1]) {
            if (intervals[i][1] > out[k - 1][1]) out[k - 1][1] = intervals[i][1];
        } else {
            out[k][0] = intervals[i][0];
            out[k][1] = intervals[i][1];
            k++;
        }
    }
    return k;
}

#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> mergeIntervals(vector<vector<int>> intervals) {
    sort(intervals.begin(), intervals.end()); // by start (then end)
    vector<vector<int>> merged;
    for (auto &iv : intervals) {
        if (!merged.empty() && iv[0] <= merged.back()[1]) {
            merged.back()[1] = max(merged.back()[1], iv[1]); // overlap
        } else {
            merged.push_back(iv);
        }
    }
    return merged;
}

Complexity

Without sorting you're stuck at O(n²). The sort is the entire reason this collapses to near linear — the pass itself never looks backward.

When to use it

Practice

Recap

• Interval problems look like all-pairs comparisons but become a single linear sweep once you sort by start time — the "sort, then exploit adjacency" pattern for pairs.
• Merge when the next interval starts at or before the current block's end; otherwise commit a block and start fresh. Watch the <= vs < boundary.
• The same sort-then-sweep skeleton solves insert, overlap-detection, and room-scheduling variants; choose start-key or end-key by the greedy goal.