Intervals: Sort First, Then Sweep

An interval is two numbers, a start and an end, and problems about them feel fiddly until you sort them. Left in input order a pile of intervals is chaos; sorted, almost every question becomes a single left-to-right sweep comparing each interval to the one just before it. What actually varies from problem to problem is the question being asked about overlap — do any two collide, how few can you delete to stop all collisions, how many pile up at the busiest moment — and each of those three questions wants the intervals sorted a particular way.

The overlap test is worth pinning down once, because it’s the primitive everything else builds on. Two intervals [a, b] and [c, d] overlap when neither ends before the other starts — a <= d && c <= b. Once the list is sorted by start, that collapses to a single check against the running frontier: the next interval overlaps if its start is <= the largest end you’ve seen.

Sort by start, then merge or check

Most of these sort by start and sweep once — an $O(n \log n)$ sort followed by an $O(n)$ pass, so the sort is where the time goes. Merge Intervals keeps a “current” interval and, for each next one, either extends its end (they overlap) or emits it and starts fresh:

intervals.sort((x, y) -> Integer.compare(x[0], y[0]));   // not x[0] - y[0]: that can overflow
List<int[]> merged = new ArrayList<>();
for (int[] cur : intervals) {
    int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
    if (last != null && cur[0] <= last[1]) {
        last[1] = Math.max(last[1], cur[1]);   // overlap: absorb into the current run
    } else {
        merged.add(cur);                        // gap: start a new run
    }
}

Meeting Rooms — “can one person attend all of these?” — is the same sort followed by a check that no neighbor overlaps at all. Insert Interval is the exception that skips the sort entirely: the list is already ordered, so you copy everything before the new interval, merge the stretch it touches, and copy the rest, all in one linear pass.

Sort by end when you’re being greedy

Non-overlapping Intervals asks for the fewest removals to kill all overlaps, which is the classic interval-scheduling problem in disguise: keep as many non-overlapping intervals as possible, and remove the rest. The greedy move is to sort by end and always keep the interval that finishes earliest, because finishing early leaves the most room for whatever comes next. Sorting by start would lead you astray here — a long interval that starts first can swallow the room two short ones needed — so end-sorting isn’t setup for this one, it’s the step that makes the greedy choice correct.

Counting how many overlap at once

Meeting Rooms II wants the minimum number of rooms, which is exactly the maximum number of meetings happening at the same instant. Two ways to get it, and both are worth knowing. Sweep-line: pull the starts and ends into two sorted arrays and walk them together, +1 on a start, -1 on an end, tracking the running peak. Or a min-heap of end times: for each meeting in start order, pop the earliest end if that room has already freed up (reusing it), then always push this meeting’s end back on — the largest the heap ever grows is your room count. Minimum Interval to Include Each Query is the hard cousin — sort queries and intervals together and use a heap keyed by interval length.

You have booked a meeting room

Scheduling software runs these exact algorithms. A calendar detecting a double-booking is running the overlap test; a room-booking system computing “how many rooms do we need at 2pm” is solving Meeting Rooms II; a scheduler reasoning about how many VMs with overlapping lifetimes sit on a host is counting concurrent intervals (real placement weighs CPU and memory too, but that time-overlap piece is exactly this problem). The overlap test you’d write for Meeting Rooms is the one a booking system runs before it confirms your 2pm slot.

When the endpoints touch

The quiet trap in every one of these is whether a shared endpoint counts as an overlap. Do [1, 2] and [2, 3] overlap? For Merge Intervals the usual answer is yes — you want [1, 3] — so the test is cur[0] <= last[1]. But Meeting Rooms treats a meeting ending at 2 and another starting at 2 as no conflict, so the same comparison has to become a strict <. Nothing else in the code changes; that single character is the difference between a right answer and an off-by-one. It’s the interval bug I’ve most often watched sail through the sample tests and then die on a boundary case, so I now read the problem’s wording for it deliberately instead of defaulting to whichever comparison I typed first.

One test, three questions

Reduced to a habit, this whole category is a single primitive — the overlap test — asked three ways. Do any intervals collide? Sort by start and sweep for a touch. How few can you delete to remove every collision? Sort by end and greedily keep the earliest-finishing. How many overlap at the busiest instant? Run a sweep-line count or a heap of end times. Name which of those three the problem is really asking, and the sort order and the loop both fall out of the answer.

References

• NeetCode 150 — Intervals — the six problems, sorted here by which sort they need.