Intervals

You’ll recognise it when

• The input is a list of ranges: [start, end] pairs for meetings, bookings, time slots, segments of a line.
• You need the union (“which times is somebody busy?”), the overlaps, or the gaps between them.
• The question asks how many things happen at the same time (rooms, servers, platforms), or how few you must remove so nothing overlaps.
• Checking every pair would work, but that’s O(n²) and n is 10⁵.

It’s close to greedy scheduling, and many interval problems are exactly that: after sorting, one pass with a simple rule decides everything. The trick is choosing what to sort by, the start or the end.

The idea

Think of a week of meetings written on sticky notes in random order, and you want to know the stretches when you’re busy. Shuffled, it’s hopeless: the meeting that overlaps Monday 9:00 could be anywhere in the pile. So you sort the notes by start time. Now you walk through them once, holding one “busy block” in your hand. Each note either starts before your block ends (stretch the block) or after it (put the block down for good and start a new one).

The key insight: once the notes are sorted by start, an interval can only overlap the block you’re holding. Every earlier block ended before something that started later than it, so nothing after can reach back to it.

How it works

We’ll merge a list of closed intervals: [1, 3] covers 1, 3 and everything between. That means [1, 3] and [3, 5] touch at 3, and they merge. (If your intervals are half-open, like meetings where one ending at 3 frees the room for one starting at 3, change <= to < and they stay separate.)

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the intervals: try one inside another, several identical ones, or a chain of touching ones.

Why it’s correct: after each step, merged is exactly the union of the intervals seen so far, and every entry except last ends before the current start. Since later intervals start even further right, an entry that isn’t last can never be touched again. So when a gap appears, closing last for good is safe.

def merge(intervals):
    """Merge overlapping closed intervals. Touching ones, like [1, 3] and [3, 5], merge too."""
    if not intervals:
        return []
    intervals = sorted(intervals)
    merged = [list(intervals[0])]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

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

// Merge overlapping closed intervals. Touching ones, like [1, 3] and [3, 5], merge too.
vector<array<int, 2>> merge(vector<array<int, 2>> intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());
    vector<array<int, 2>> merged = {intervals[0]};
    for (size_t i = 1; i < intervals.size(); i++) {
        auto [start, end] = intervals[i];
        auto& last = merged.back();
        if (start <= last[1]) {
            last[1] = max(last[1], end);
        } else {
            merged.push_back({start, end});
        }
    }
    return merged;
}

import java.util.*;

class Intervals {
    // Merge overlapping closed intervals. Touching ones, like [1, 3] and [3, 5], merge too.
    static List<int[]> merge(int[][] intervals) {
        List<int[]> merged = new ArrayList<>();
        if (intervals.length == 0) return merged;
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
        merged.add(sorted[0].clone());
        for (int i = 1; i < sorted.length; i++) {
            int start = sorted[i][0], end = sorted[i][1];
            int[] last = merged.get(merged.size() - 1);
            if (start <= last[1]) {
                last[1] = Math.max(last[1], end);
            } else {
                merged.add(new int[]{start, end});
            }
        }
        return merged;
    }
}

Why it’s O(n log n)

Sorting takes O(n log n). The sweep looks at each interval once and does O(1) work on it, so it’s O(n). Sorting dominates.

The output can hold up to n intervals, so space is O(n), plus whatever the sort uses. If the input is already sorted, the whole thing is O(n).

Common mistakes

last[1] = end                  # ✗ [1, 10] then [2, 3] gives [1, 3]
last[1] = max(last[1], end)    # ✓ the end only ever grows

if start <= intervals[i - 1][1]:   # ✗ misses long intervals further back
if start <= merged[-1][1]:         # ✓ compare with the block you're building

merged.append(interval)            # ✗ later edits change the input too
merged.append([start, end])        # ✓ a fresh list

Variations

• Insert an interval. The list is already sorted and non-overlapping, and one new interval arrives. Copy the intervals that end before it starts, then fold every interval that overlaps it into it with min and max, then copy the rest. One pass, O(n), no sort.
• Meeting rooms (most overlap at once). Turn each meeting into two events, (start, +1) and (end, -1), sort them, and keep a running sum: its peak is the number of rooms. For half-open meetings, sort an end before a start at the same time, so a room is freed before it’s reused. Or sort by start and keep a min-heap of end times: pop the earliest end if it’s <= start, push the new end; the heap’s largest size is the answer.
• Fewest removals so none overlap. This one sorts by end. Keep the interval that ends first, skip everything that starts before it ends, repeat. Finishing early leaves the most room for the rest, so the kept count is the maximum, and the answer is n minus it.
• Intersection of two lists. Given two sorted, non-overlapping lists, use two pointers. The overlap of a and b is [max(a0, b0), min(a1, b1)] when that’s non-empty. Then advance whichever interval ends first, since it can’t overlap anything else.
• Small integer coordinates. When the ends are integers up to about 10⁶, skip sorting: add +1 at each start and −1 just after each end in a difference array, and a prefix sum gives how many intervals cover every point.