How does a min-heap of end times find the minimum number of servers a set of scheduled campaign flights needs?
answer
- Process the flights in start order
- Keep the live ones somewhere ordered
- Only the earliest finisher can be released
- Every later start is at or after this one
- The peak count is the answer
basics
~20 sSort the flights by start time, then walk them keeping every currently-running end time in a min-heap. Before each flight, pop all end times at or before its start; push its own end. The largest heap size seen is the answer.
solid answer
~50 sSort the campaign flights by start time, then sweep them in that order with a min-heap holding the end times of flights still running. For each flight, first pop every heap entry whose end is `<=` this flight's start — those campaigns are provably finished, because every remaining flight starts at or after the current one — then push this flight's own end. The heap size after the push is how many campaigns are simultaneously live at that instant, and the maximum size across the whole walk is the minimum number of servers required. Only the *earliest* end can ever be releasable, which is exactly why a min-heap suffices instead of rescanning all active flights. Cost is `O(n log n)` for the sort plus `O(n log n)` for the heap traffic, with `O(k)` extra space where `k` is the peak.
code
pseudocode · 12 linessort flights by start ascending
H = empty min-heap of end times
peak = 0
for i in 0..length(flights)-1
s = flights[i].start
e = flights[i].end
while H is not empty and heap_min(H) <= s
heap_pop(H)
heap_push(H, e)
if size(H) > peak
peak = size(H)
return peakgo deeper
Know that the answer is the peak number of things running at once, not the total count and not the number of overlapping pairs. Be able to sketch the sort-by-start walk and say what the heap holds.
Explain why popping ends at or before the current start is provably safe, and why only the smallest end ever needs checking. State the cost as sort plus heap traffic and name the auxiliary space.
Show that you can vary the shape for the job: pop-all with a running maximum when you need the count, pop-one when the heap should model the allocated resources themselves. Say how the boundary convention lands in the pop comparison.
Own the framing: peak concurrency is the provisioning floor, not the operating target. Be ready to argue for headroom, for what happens when a flight overruns its declared end, and for whether the schedule is even known in advance.
## The question behind the algorithm An ad platform schedules **campaign flights**: each flight has a start and an end, and while it is live it needs one dedicated server instance. Instances are interchangeable and reusable — the moment a flight ends its instance can serve another flight. How many instances must be provisioned so that no flight is ever left without one? The answer is the **peak number of simultaneously live flights**. Not the total number of flights, and not the number of overlapping pairs. ## The walk 1. Sort the flights by start time ascending. 2. Keep a min-heap of the end times of flights that are currently live. 3. For each flight in start order: pop every heap entry with `end <= this.start`, then push `this.end`. 4. Track the maximum heap size observed; that maximum is the answer. ## Why popping is safe — the invariant that carries the whole proof The flights are processed in non-decreasing start order, so **every flight not yet processed starts at or after the current flight's start**. If a heap entry's end is `<= current.start`, that campaign has finished before the current flight begins, and therefore before every remaining flight begins too. Its instance can never be needed again by anything still to come. Freeing it is not a heuristic — it is provably correct, and it cannot be premature. The converse matters just as much: if the *smallest* end in the heap is greater than the current start, then no end in the heap is `<= current.start`, so nothing can be freed and the loop stops immediately. That is the entire reason a min-heap earns its place here. Any structure that could hand you the minimum end in logarithmic time would do; a plain list would force a linear rescan of all live flights on every step and drag the walk toward quadratic when many flights are live at once. ## The wrong answer this question is aimed at A frequent attempt is: sort by start, then count how many *adjacent* pairs overlap. That measures pairwise adjacency, not simultaneity. Three flights that all run 10:00–18:00 give two adjacent overlapping pairs but need three instances; overlap stacks transitively and a pairwise count cannot see the stack. A second wrong turn is to answer with the number of overlapping pairs overall, which is a different quantity entirely — it can be quadratic in the number of flights while the required instance count stays small. ## Two shapes of the same walk The version above pops *every* finished end and reports the maximum heap size. There is a second, equally correct shape: pop **at most one** finished end per flight, then push. In that variant the heap stops modelling "flights currently live" and starts modelling "instances allocated": each entry is one instance, storing the time it next becomes free. A new flight either reuses the earliest-freed instance or forces a new one. Because the heap then never shrinks, its final size *is* the answer, with no running maximum to track. The second shape is the one to reach for when the assignment itself matters, since each heap entry can carry an instance identifier alongside its end time. Both are optimal, and the reason is the same: the peak is a lower bound (at the busiest instant, that many flights are live simultaneously and no two can share an instance), and the walk never allocates more than the peak. ## Cost Sorting dominates at `O(n log n)`. Each flight is pushed once and popped at most once, so heap traffic is `O(n log n)` overall — amortised across the whole walk, not per step, since one step may pop many entries while another pops none. Auxiliary space is `O(k)`, where `k` is the peak concurrency, which is often far below `n`. If the flights arrive already sorted by start — very common, since schedules are usually stored in start order — the whole thing collapses to a linear pass plus logarithmic heap work. ## Boundaries and traps - **The comparison in the pop condition encodes the boundary convention.** With half-open ranges, `end <= start` means a flight ending exactly when another begins releases its instance in time, so `<=` is right. Under closed semantics it must be `<`, or you will hand one instance to two campaigns that share an instant. - **Sorting by end time instead of start breaks the invariant.** The proof depends on "every remaining flight starts at or after this one"; end order gives you no such guarantee. - **Equal starts need no tie-breaking.** Flights with identical starts are all pushed before any of them can be popped, so the peak is counted correctly whatever order they appear in. - **The heap holds ends, not whole flights,** unless you need identity. Storing the end alone keeps comparisons trivial and the structure small.
- Why not just scan the list of live flights for a finished one instead of using a heap?Correctness would be unaffected, but cost would not. Only the earliest end can be releasable, so a structure that surfaces the minimum in logarithmic time answers the question in one look; a plain list forces a linear rescan of every live flight at each step. When many flights run at once that pushes the walk toward quadratic time, which is exactly the case the schedule gets large enough to care about.
- What does the running maximum give you that the final heap size does not?In the pop-everything variant the heap shrinks whenever campaigns finish, so its size at the end reflects only the last busy stretch, not the busiest one. The maximum over the walk is the peak concurrency and hence the required instance count. The alternative is the pop-at-most-one variant, where the heap models allocated instances rather than live flights, never shrinks, and so reports the answer as its final size.
- The flights arrive already sorted by start time. What is the cost then?The sort disappears and the walk becomes a single linear pass with `O(log k)` heap work per flight, where `k` is the peak concurrency — `O(n log k)` overall, and `O(n)` when the peak is small and bounded. Space stays `O(k)`. This is a common real situation, since schedules are usually persisted in start order, and it is worth naming: the sort is the dominant cost only when the input arrives unordered.
saying these in an interview costs you the question
- Counts adjacent overlapping pairs and calls it the peak
- Answers with the number of overlapping pairs rather than the peak count
- Sorts by end time and claims the pop rule still holds
- Uses the final heap size after popping every finished end
- Calls the heap work O(n) per step instead of amortised across the walk
- Uses a strict < in the pop test on half-open ranges, over-provisioning