Intervals & Sweep Line

Why this topic is smaller than it looks

Intervals rarely get their own dedicated grind session, yet they show up constantly: calendar scheduling, resource allocation, range-merging, log analysis. The reason they're grouped into a single topic here is that almost every interval problem — "merge", "insert", "how many rooms", "how many arrows", "which intervals overlap" — reduces to one of two closely related templates:

1. Sort by start (or end), then linear-scan while comparing each interval to a running "current" state.
2. Convert intervals into +1/-1 events, sort the events, and sweep through while tracking a running counter.

Master these two templates and their tie-breaking rules, and the entire interval family collapses from "dozens of distinct problems" into "one decision: which template, and which sort key." This is also why Intervals sits right after Greedy on this roadmap — the classic interval-scheduling greedy proof ("always pick the interval that finishes earliest") is the theoretical justification for why sorting by end works — and why Heaps comes up constantly as the data structure that generalizes the counter into "which resource is free soonest."

Template 1: sort-and-scan (merge / insert / non-overlapping)

The mental model: after sorting by start time, if interval B starts after interval A ends, then every subsequent interval (they all start at or after B's start) also starts after A ends. A is therefore "closed out" — no future interval can ever touch it again. This monotonicity is what licenses a single left-to-right pass instead of comparing every pair.

Two variants of this same template you should recognize on sight:

• Insert into a sorted, non-overlapping list (à la "Insert Interval"): instead of sorting, exploit that the list is already sorted — walk it in three phases: intervals entirely before the new one (copy as-is), intervals that overlap the new one (fold into it by taking min-start/max-end), intervals entirely after (copy as-is). This is O(n), not O(n log n), precisely because you skip the sort.
• Minimum removals for non-overlap ("Non-overlapping Intervals"): sort by end, not start. Greedily keep an interval if it starts at or after the end of the last kept interval; otherwise it must be removed. Sorting by end is what makes this greedy choice provably optimal — you're always keeping the option that frees up the earliest possible "runway" for future intervals. This is the direct interview link back to the Greedy topic's interval-scheduling maximization problem.

Template 2: sweep line with events

Sort-and-scan tracks one running merged interval. Sweep line generalizes this to track how many intervals are simultaneously active — the tool for "minimum meeting rooms," "maximum overlap," "is there a triple-booking," and counting-style problems.

The construction: turn every interval [start, end] into two events — a +1 at start and a -1 at end (or end + 1, depending on inclusivity — see below). Sort all 2n events by coordinate, then sweep left to right, maintaining a running counter. The counter's value between two consecutive events tells you exactly how many intervals are active in that gap; its maximum over the whole sweep is your answer.

The tie-break subtlety (a top interview bug source)

When a start-event and an end-event land on the same coordinate, the order you process them in silently encodes your definition of "overlap":

Interval convention	Tie-break rule	Effect on [1, 5] and [5, 9]
Inclusive endpoints, touching counts as overlap (e.g. [1,5] and [5,9] share point 5)	Process starts before ends at equal coordinates	Counter hits 2 at t=5 — correctly flags the overlap
Half-open [start, end), touching does not count as overlap (e.g. meetings back-to-back at the same time)	Process ends before starts at equal coordinates	Counter drops to 0 before rising back to 1 at t=5 — correctly shows no conflict

There's no universally "correct" tie-break — it depends entirely on the problem's boundary semantics, which is exactly why you should state your assumption out loud in the interview before coding ("I'm treating a meeting ending at 5 and one starting at 5 as non-conflicting, so I'll process end-events first"). Getting this backwards is the single most common silent-off-by-one bug in interval problems, because it doesn't crash — it just gives a subtly wrong count that only shows up on edge-case tests.

A common alternative that sidesteps the tie-break entirely: encode the end-event at end + 1 instead of end when endpoints are inclusive and touching doesn't count as overlapping. That converts a same-coordinate tie into strictly ordered events and removes the ambiguity outright — worth having as a fallback if the tie-break logic gets confusing mid-interview.

The heap variant

When you need to know not just the count of active intervals but which one is which (e.g., which resource becomes free soonest so you can reassign it), swap the +1/-1 counter for a min-heap keyed by end time. Sort intervals by start; for each new interval, pop-while the heap's smallest end time is ≤ the new interval's start (that resource is now free) — otherwise push a new resource. The heap's final size is the answer, and this is precisely the pattern the Heaps & Priority Queues topic drills in depth for "minimum meeting rooms"-style questions where sweep-line counting alone doesn't track identity.

Comparison: which template to reach for

Signal in the problem	Template	Sort key	Complexity
"Merge overlapping intervals", "insert into sorted list"	Sort-and-scan, track one running interval	Start	O(n log n) time, O(n) space
"Minimum intervals to remove for non-overlap", "max non-overlapping intervals"	Sort-and-scan, greedy keep/reject	End	O(n log n) time, O(1) extra space
"Max simultaneous overlap", "minimum rooms/resources", "is there a conflict at all"	Sweep line with +1/-1 events	Event coordinate (with explicit tie-break)	O(n log n) time, O(n) space
"Minimum rooms AND which room is reused"	Sweep line + min-heap keyed by end time	Start (heap keyed by end)	O(n log n) time, O(n) space

Complexity analysis

Every variant above is dominated by the same term: sorting is O(n log n), and the subsequent scan (whether it's a linear pass or a heap-driven sweep) is O(n) or O(n log n) if each of the n elements triggers an O(log n) heap operation. You will essentially never beat O(n log n) overall on interval problems unless the input arrives pre-sorted (as in "Insert Interval," which is why that variant achieves O(n)). State this proactively: "This is O(n log n), dominated by the sort — the scan itself is linear."

Common pitfalls and edge cases

• < vs <= at the overlap check. Whether [1, 3] and [3, 5] overlap depends entirely on the problem's stated convention. Ask, don't assume — and once you decide, apply it consistently at both the merge-check and the sweep-line tie-break.
• Forgetting to update the merged interval's end to max(...), not just the new interval's end. [1, 10] merged with [2, 3] must stay [1, 10], not shrink to [2, 3].
• Sorting by the wrong key. Sort-and-scan-to-merge needs start-sorted input; the non-overlapping-removal greedy needs end-sorted input. Mixing these up silently produces a plausible-looking but wrong answer.
• Empty input and single-interval input. Both are trivially valid — an empty list merges to an empty list, and a single interval both "merges" and has zero overlap by definition. Say it, handle it in one line, move on; interviewers are checking that you don't skip it, not that you write elaborate logic for it.
• Unsorted input in disguise. Many problem statements don't explicitly say "intervals are sorted" — verify the constraints rather than assuming, since skipping the sort when it's actually required is a silent correctness bug, not a crash.
• Integer overflow / off-by-one on end + 1 tie-break tricks. If you shift end-events to end + 1 to dodge the tie-break question, make sure that doesn't collide with another interval's legitimate start at that exact coordinate under a different convention.

What to keep in long-term memory (1-month flashcard)

Forget LC numbers; retain these principles — they cover almost every interval ask:

1. Overlap test. [x1, x2] and [y1, y2] overlap iff max(x1, y1) ≤ min(x2, y2) (or < if touching must not count). Decide the boundary convention out loud before coding.
2. Only two templates. Sort-and-scan (merge / insert / arrows / non-overlap greedy) vs sweep with +1/-1 events (concurrency / rooms / max overlap). Heap = sweep when you need which resource frees soonest, not just a count.
3. Sort key is the whole game. Merge / left-to-right scan → sort by start. Max compatible / min removals / min arrows (“finish early”) → sort by end. Wrong key → confident wrong answer.
4. Monotonic discard. After sorting, if B starts after A ends, nothing later can touch A. That is why one pass beats pairwise checks — never rewind.
5. Greedy principle. For “max non-overlapping” / “min shots to cover”: take or shoot the option that finishes earliest (exchange argument). Arrows: sort by end, shoot at current end, skip everything that still covers that point.
6. Sweep tie-break. Same coordinate: start-before-end vs end-before-start is your touching semantics. State it; getting it backwards is the classic silent bug.
7. Two sorted lists. Two pointers; advance the interval that ends first. No j -= 1 rewind — if you feel you need to backtrack, the pointer rule is wrong.

One-liner to rehearse: Intervals = sort (start or end?) → one pass. Overlap = max L ≤ min R. Touching? Say it. Tie-break? Say it.

How to state this in an interview

"I'll sort intervals by start time, then do a single pass tracking the current merged interval — that's O(n log n), dominated by the sort. Since intervals [a, b] and [b, c] count as overlapping here, I'll merge when the next start is less than or equal to the current end."

Naming the sort key, the tie-break convention, and the complexity bound in one breath is exactly the signal that separates "recognized the pattern" from "actually understands why it's correct" at a Senior bar.