Topic notebook / 10
Intervals & scheduling
Sorted starts and ends let you merge overlaps, select compatible intervals, or count simultaneous meetings.
What to look for
- State whether touching endpoints overlap.
- Sort before scanning.
- Distinguish merging, selecting and counting occupancy.
Work through a question
5 availableAdd a Closed Coverage Span
Given {"intervals":[[start,end],...],"new":[start,end]}, insert a closed coverage span and coalesce all overlap. Existing spans must be sorted and already separated: each next start must exceed the previous end. Touching endpoints count as overlap. Every span has start < end.
Medium / Three-phase interval scan / interactiveCoalesce Closed Coverage Spans
Given unsorted closed [start,end] coverage spans, return their sorted coalesced union. Touching endpoints merge, nested spans do not create new output rows, and each input start is strictly less than its end.
Medium / Sort by start and extend / interactiveDrop the Fewest Reservations
Reservations use half-open [start,end) times with start < end. Return the minimum number to discard so one resource can accept all remaining reservations. Ending exactly when another starts is compatible.
Medium / Greedy earliest finish / interactiveCan One Guide Attend Everything?
A guide has unsorted half-open [start,end) appointments. Return an explicit boolean for whether one guide can attend every appointment. Each start < end; an appointment ending at the next start is allowed.
Easy / Sort and compare neighboring spans / interactiveProvision the Fewest Workshop Rooms
Workshops use unsorted half-open [start,end) spans. Return the fewest rooms needed for all workshops. Each start < end; a room is free at its ending time and can be reused immediately.
Medium / Min-heap of active ending times / interactiveWhere this leads
Return to the roadmap to try a different kind of problem.