Heaps and Priority Queues
The interval problem that needed a heap
Deferred from Unit 6 on purpose. Sort the queries, sweep the intervals, and keep the live ones in a heap.
Key idea
Why this waited
Unit 6 covered sorting intervals, merging them, and sweeping through events. It deliberately left one problem out: for each of many query points, report the size of the smallest interval covering that point.
The sweep is familiar. What was missing is a structure that can hand you the smallest live interval at any moment, and that is a heap.
Why it works
Answer the queries in a different order than asked
The queries arrive in arbitrary order and the answers must be returned in that order. Nothing says you have to compute them in that order.
Sort the queries ascending, sweep through them, and remember each answer against its original position. Restoring the original order at the end is bookkeeping. Being allowed to reorder the work is what makes the sweep possible at all, and this technique has a name worth knowing: answering queries offline.
The sweep
Sort the intervals by start. Walk the sorted queries, and for each one: add every interval that has started by now, discard from the top every interval that has already ended, then read the smallest remaining.
Below is what that looks like at a single query point, with the intervals added by hand instead of by a moving index.
Why it works
Why discarding from the top is enough
A heap cannot remove an arbitrary element, and the expired intervals are not necessarily at the top. That sounds fatal and is not.
The only thing ever read is the top. So an expired interval buried in the middle causes no harm; it will be discarded when it eventually surfaces. Discarding from the top until the top is valid is enough to guarantee the answer is correct.
This is called lazy deletion, and it is the standard way to work around a heap's inability to remove from the middle. Each interval is pushed once and popped at most once, so the total cost stays bounded even though the heap may temporarily hold junk.
Tip
Both while loops only ever move forward
Queries are processed in ascending order, so the set of started intervals only grows and the set of expired ones only grows. Neither loop ever has to undo anything.
That monotonicity is what makes the whole thing linear in the number of pushes and pops, and it is why sorting the queries was the enabling step rather than a convenience.
Gotcha
Remember to restore the original order
Answers are computed in sorted-query order and must be returned in the caller's order. Writing into answers[index] rather than appending is what handles that.
Appending and returning would give correct values in the wrong positions, which passes any test whose queries happen to arrive sorted. Include an unsorted query list in your own testing.
Predict the output: answering out of order and restoring it
The queries have to be answered in the order they were asked, but nothing says they have to be computed in that order. Type the two lines it prints.
Minimum Interval To Include Each Query
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.