For peak concurrent bookings, when must you keep a min-heap of end times instead of counting boundary events?
answer
- Both cost the same asymptotically
- Ask what each structure remembers
- One yields a number, one yields entries
- Which resource, not how many
- Greedy reuse assumes interchangeable resources
basics
~20 sKeep the heap when you need to know which resource each booking got, or to carry per-resource state. If only the peak number matters, counting boundary events in time order answers it with less code, less memory and smaller constants.
solid answer
~50 sBoth approaches are `O(n log n)`, dominated by the same sort, so the choice is not asymptotic — it is about what the structure remembers. Counting boundary events yields a running number and nothing else: cheap, tiny, and exactly right when the question is "how many rooms do we need?". A min-heap of end times keeps one live entry per occupied resource, so each entry can carry an identifier and per-resource state, which is what you need to answer "which room did this booking get?", to report a per-resource utilisation breakdown, or to stream assignments as bookings arrive. I default to the counting scan for a capacity number and reach for the heap the moment identity or per-resource attributes enter the requirements — and I say clearly that the heap's greedy earliest-free rule is optimal only while the resources are genuinely interchangeable.
go deeper
Know that both approaches answer the same peak-count question and that the sort dominates the cost of each. Be able to say the heap holds end times of live bookings while the counting scan holds only a number.
Explain what each structure remembers and why identity is the deciding factor. Be ready to describe the heap variant whose entries model allocated resources rather than live bookings.
Make the call against a stated requirement and defend it on maintenance cost and information content, not speed. Name the interchangeability assumption behind greedy reuse and what happens when it fails.
Own the requirement conversation. Decide whether the system owes callers a capacity figure or an assignment, treat peak concurrency as a provisioning floor rather than a target, and be explicit about when heterogeneous resources turn this into a different problem class.
## Two structures, one number Both approaches answer "what is the largest number of bookings live at the same instant?", and both are `O(n log n)` because both must put the data in time order first. The scan that counts boundary events walks the ordered boundaries and keeps a running count, reporting its maximum. The min-heap walk processes bookings in start order and keeps the end times of live bookings, reporting the maximum heap size. Same answer, same asymptotic cost. So the interesting question is not which is faster. It is **what each structure remembers**, and that is a genuine selection trade-off. ## What each one gives you | | Boundary counting | Min-heap of end times | |---|---|---| | Answers "how many?" | Yes | Yes | | Answers "which resource?" | No | Yes — one entry per resource | | Per-resource state | None | Attached to the entry | | Extra space | The ordered boundaries | `O(k)`, the peak concurrency | | Code surface | A counter and a maximum | A heap plus its ordering | | Streaming input | Needs all boundaries first | Assigns as bookings arrive, in start order | The counting scan discards identity by construction: it reduces every booking to two anonymous marks on a timeline and then adds them up. That is its virtue — nothing to maintain, nothing to get wrong, constants small enough that it will beat the heap on the same input even though the asymptotics match. The heap keeps one live object per occupied resource. That object can hold an identifier, a cleaning-crew assignment, a next-available timestamp, a capability tag. The moment the requirement mentions *which*, the heap is the structure that already knows. ## The requirements that force the heap - **Assignment output.** "Give each booking a room number" is not answerable from a count. Use the variant that pops at most one freed entry per booking and reuses its identifier: the heap then models allocated rooms rather than live bookings, and its size is the room count while its entries are the assignment. - **Per-resource reporting.** Utilisation per room, turnover time per room, which room was busiest — all need per-resource state that the counting scan never materialises. - **Incremental or streaming operation.** If bookings arrive in start order and each must be assigned on arrival, the heap does that in one pass. The counting scan can maintain a live count too, but it can never say *which* resource is free. - **Anything downstream keyed by resource.** Cleaning schedules, equipment moves, staff rosters — they consume assignments, not a number. ## When counting is the right answer and the heap is over-engineering Capacity planning usually wants a number: how many rooms must exist, what the peak load on a service is, whether a fleet is over-provisioned. Here the counting scan is less code to maintain and less state to get wrong, and the difference is not academic — the heap version has two extra ways to be subtly incorrect (the boundary convention in its pop comparison, and confusing final heap size with the running maximum). Reaching for the heap because it is the more interesting structure is a real cost paid by whoever maintains the code. ## The limit worth naming The heap's greedy rule — give the incoming booking the earliest-freed resource — is optimal **only when resources are interchangeable**. Once rooms differ in capacity, equipment, or accessibility, and bookings have requirements, "earliest free" can hand out a room that a later booking needed, and the greedy is no longer a minimum. That problem is a matching problem, not an interval problem, and a candidate who notices the boundary is showing exactly the judgment the question is looking for. Conversely, the *peak count* remains a valid lower bound on how many resources are needed no matter how heterogeneous they are — it just stops being achievable. ## How to state the choice in an interview Name that both are `O(n log n)` and dominated by the sort, so the decision is about information rather than speed. Then say what each remembers, and pick against the actual requirement: a number gets the counting scan; an assignment gets the heap. Finish with the constraint — interchangeable resources — under which the heap's greedy allocation is provably minimal, because that is the assumption the whole approach silently rests on.
- If both are O(n log n), on what grounds would you ever prefer the counting scan?Maintenance cost and constants. The counting scan is a counter and a maximum over ordered boundaries — almost nothing to get wrong — while the heap version adds a structure whose pop comparison encodes the boundary convention and whose reported answer depends on which variant you wrote. When the requirement is a capacity number, the extra machinery buys nothing and costs a reviewer's attention on every change.
- Rooms differ in capacity and equipment, and bookings state requirements. Does the heap approach still give the minimum?No. Giving the incoming booking the earliest-freed room is optimal only when rooms are interchangeable; with requirements, that room may be the one a later booking uniquely needed. The problem becomes a matching problem rather than an interval problem. The peak concurrency figure still stands as a lower bound on how many rooms are required, but it is no longer necessarily achievable, and the gap is exactly what the matching has to close.
- Bookings stream in, in start order, and each needs a room assigned on arrival. Which do you use?The heap, in the variant where each entry is an allocated room holding the time it next becomes free. On each arrival, reuse the earliest-freed room if it is free by now, otherwise allocate a new one. That produces the assignment immediately and keeps the room count minimal for what has been seen so far. A counting scan can maintain the live number under streaming too, but it can never say which room to hand over.
saying these in an interview costs you the question
- Claims one approach is asymptotically better than the other
- Reaches for the heap when the requirement is only a capacity number
- Says a running count can report which resource a booking received
- Assumes earliest-free greedy stays optimal when resources differ
- Ignores that both are dominated by the same initial sort
- Treats peak concurrency as an operating target rather than a floor