latency.lab
Algorithms · Topic 15

Intervals

Level: foundationTool: sort-then-sweep over interval boundariesTime: ~75 min

By the end you can

Interval problems share a shape you'll recognize immediately once you've seen it: sort the intervals by some key, then make a single linear pass. The entire skill in this topic is picking the right sort key and the right thing to track during that pass — get those two decisions right and the rest nearly writes itself.

Sort by start: building up a result

Merge Intervals is the cleanest version of this shape: sort by start, then walk the list extending a "current" merged interval whenever the next one overlaps it, or closing it and starting a new one when it doesn't. Insert Interval is the same idea applied to inserting one new interval into an already-sorted list in a single O(n) pass — copy everything strictly before it, absorb everything it overlaps, copy everything strictly after.

[1,3] [2,6] [8,10]
↓ merge overlapping
[1,6] [8,10]
[1,3] and [2,6] overlap (2 falls inside [1,3]) and merge into [1,6]; [8,10] doesn't touch either, so it stays separate. Sorting by start first is what guarantees every interval that could possibly overlap the "current" merged one is checked immediately next, in order.

Sort by end: greedy selection

Non-overlapping Intervals and Minimum Number of Arrows to Burst Balloons both need the *other* sort key. This is the classic "activity selection" greedy: when two intervals conflict, keep whichever one ends earlier — it leaves strictly more room for everything that comes after it than any other choice would. Sorting by start instead is the natural first instinct, and it's provably wrong: a long interval that happens to start early can look worth keeping, when discarding it would have left more room overall.

The habit to build

Before writing any interval solution, ask: does correctness here depend on which interval starts first, or which one finishes first? Merging and inserting care about start order. Greedy selection — picking the maximum number of non-conflicting intervals — almost always cares about end order instead.

Sweep line: counting what's active at once

Meeting Rooms II answers "what's the peak number of intervals overlapping at any single instant?" by splitting every interval into two separate events — a start and an end — sorting all of them together, and sweeping through in order while tracking a running count. A start increments the count, an end decrements it, and the maximum value the count ever reaches is the answer. Car Pooling is the exact same sweep, just counting passengers instead of meetings — and it adds one more wrinkle: at a tied location, a drop-off (decrement) must be processed before a pick-up (increment), since a passenger leaving frees a seat before a new one at that same stop needs it.

Two pointers across two separate lists

Interval List Intersections merges two already-sorted, already-non-overlapping interval lists with two pointers instead of one: compute the overlap between the current interval from each list, record it if valid, then advance whichever one ends first — it can't possibly overlap anything further along in the other list either, so it's safe to move past.

When a sorted structure beats scanning everything

My Calendar I checks a new booking against every previously booked event — done naively, that's O(n) work per booking. Keeping the booked events in a std::set ordered by start time turns each check into O(log n): lower_bound finds the one neighboring event on each side that could possibly conflict, without ever looking at anything else. Minimum Interval to Include Each Query pushes this further, combining a sort with a min-heap (the same "keep only what's still relevant" idea as heaps from that earlier topic) to answer every query in O(log n) amortized instead of rechecking every interval per query.

Common mistakes

  • Sorting by start when the greedy argument needs end — Non-overlapping Intervals and Minimum Arrows both silently produce a wrong (too-large) count if sorted by start instead.
  • Missing a required tie-break — Remove Covered Intervals needs same-start intervals sorted by end descending, or a covering interval can be processed after (instead of before) the smaller interval it covers, undercounting how many get removed.
  • Assuming one consistent rule for "touching" boundaries — Merge Intervals treats a touching pair like [1,4],[4,5] as overlapping (they merge); Meeting Rooms treats a touching pair as perfectly fine (back-to-back, no conflict). Each problem defines its own boundary semantics — read it, don't assume it.
  • Forgetting same-location event ordering — Car Pooling's drop-offs must be processed before pick-ups at an identical location, or a valid schedule gets rejected on a transient (never-actually-true) capacity spike.

Takeaways

  • Nearly every interval problem is "sort by the right key, then one linear pass" — identifying the right key is most of the work.
  • Merging/inserting sorts by start; greedy maximum-selection sorts by end (the activity-selection argument).
  • Counting concurrent overlap is a sweep over start/end events, with same-location ties sometimes needing a specific processing order.
  • Two sorted interval lists merge with two pointers, each advancing past whichever interval ends first.
  • A sorted structure (ordered set, or a heap alongside sorted queries) turns a per-check O(n) scan into O(log n) when checks happen repeatedly.

Try it: sort by start, build a result

Merge Intervals — the foundational shape every other problem in this topic riffs on.

Live

Loading starter code…

Try it: sort by end, greedy selection

Non-overlapping Intervals — the exercise that makes the start-vs-end sort key distinction concrete. Trace through the "wrong greedy" test case by hand before you look at the hint.

Live

Loading starter code…

Try it: sweep line concurrency counting

Meeting Rooms II — the clearest example of splitting intervals into separate start/end events and sweeping through them.

Live

Loading starter code…

Keep going

That's 3 of the 12 problems in this topic. Car Pooling is worth doing right after Meeting Rooms II — it's the same sweep-line idea with one extra same-location ordering trap layered on. See the full Intervals set →

Checkpoint · Intervals

5 questions · pass at 70%

Q01
Non-overlapping Intervals sorts by END time, not start time, before applying its greedy rule. Why does sorting by start time instead produce a wrong (too-large) removal count?
WhyThe activity-selection greedy argument specifically requires ending earliest, because that leaves the maximum possible room for subsequent intervals to also fit without conflict. A long interval that starts early is not the same thing as one that leaves the most room -- sorting by start can lead the greedy to keep exactly the wrong interval at a conflict, inflating the removal count above the true minimum.
Q02
Merge Intervals treats a touching pair like [1,4] and [4,5] as overlapping (they merge into [1,5]), while Meeting Rooms treats a touching pair (one meeting ending exactly when the next begins) as perfectly fine, not a conflict. What does this contrast actually teach?
WhyThere's no universal rule for how touching interval boundaries behave -- it depends entirely on what the specific problem is modeling. Merge Intervals is really asking 'do these describe one continuous range,' where touching endpoints are still continuous. Meeting Rooms is asking 'can one person physically attend both,' where a meeting ending right as the next begins is completely fine. Both are correct for what they're modeling -- the lesson is to read each problem's own definition rather than carry an assumption over from a different problem.
Q03
Remove Covered Intervals sorts by start ascending, but breaks ties by END DESCENDING rather than ascending. Why does that specific tie-break matter?
WhyThe algorithm tracks a running maximum end and considers an interval 'covered' if its end doesn't exceed that maximum. If two intervals share a start and the smaller one is processed first (end ascending), it gets counted as a new, uncovered interval before the true covering interval is ever seen -- inflating the surviving count. Sorting ties by end descending ensures the covering interval is always seen first, so anything it actually covers is correctly recognized as covered afterward.
Q04
Meeting Rooms II splits every interval into a start event and an end event, sorts all of them together, and sweeps through tracking a running count. What does that running count represent at any point during the sweep, and why does its PEAK value answer the question?
WhyIncrementing on a start event and decrementing on an end event makes the running count, at any moment during the sweep, exactly equal to how many meetings are simultaneously in progress. Since each simultaneously-active meeting needs its own room, the highest this count ever climbs during the whole sweep is precisely the minimum number of rooms that must exist to never double-book one.
Q05
My Calendar I keeps booked events in a std::set> ordered by start time and uses lower_bound to check a new booking, rather than looping over every previously booked event. Why does this specifically give O(log n) per booking instead of O(n)?
WhyBecause the set keeps events ordered by start time, a binary-search-based lookup (lower_bound) can jump directly to the one event that starts right after the new booking's start, in O(log n). That event, plus the one immediately before it in the ordering, are the only two events that could possibly overlap the new booking -- every other already-booked event is provably too far away to conflict, so there's no need to examine it at all.

Finished Intervals?

Pass the quiz to complete it automatically.