873. Serving the Highest Priority First

A print server processes a log of q operations:

add p id a job with priority p and identifier id joins the queue serve the waiting job with the HIGHEST priority is printed and leaves

If two waiting jobs share the highest priority, the one with the SMALLER identifier is served first. For every serve, print the identifier of the job served, or idle if nothing is waiting.

add 3 100, add 7 101, serve, add 7 5, serve -> 101, 5 add 2 9, add 2 3, serve, serve -> 3, 9 serve, serve -> idle, idle

The second row is the tie rule doing its work: both jobs have priority 2, so identifier 3 goes before identifier 9 even though 9 arrived first.

## What most people try first

Scanning the waiting list on every serve to find the best job. That is O(n) per serve, and with q = 200000 operations it reaches 2 * 10^10 comparisons. Keeping the list sorted by priority instead moves the same cost onto add, since an arriving job has to be inserted into the middle. Either way one of the two operations is linear.

## A max-heap, and the trick for getting one

This is problem 872 with the direction reversed, so the structure is a MAX-heap: the winner is the largest, so the root must be the largest. Turn every comparison in the sift routines around and you have one.

Most standard libraries only offer a min-heap. Two ways to borrow it:

negate: push -p, and the minimum of the negatives is the maximum comparator: C++ priority_queue and Java PriorityQueue both take one

## The tie rule is not decoration

A heap makes no promise about equal elements. Without the tie rule, two correct programs would disagree on the second example and no judge could mark either. Make the heap order pairs, not numbers:

job a beats job b when a.priority > b.priority or a.priority == b.priority and a.id < b.id

With the negation trick the whole thing becomes one ordinary min-heap over the pair (-priority, id), because smaller -priority means larger priority and smaller id breaks the tie in the right direction automatically. Getting both components pointing the same way is the part worth checking twice.

## The boundary that breaks a careless implementation

serve with nothing waiting prints idle and must not touch the heap. The log may begin with it, and it may happen several times.

## What is NOT an overflow here

Priorities reach 10^9 and identifiers reach 10^9. Both fit in a signed 32-bit integer, whose largest value is 2147483647, and nothing here is ever added or multiplied. The only trap is negation: -p for p = 10^9 is -1000000000, comfortably inside range. There is no overflow in this problem and pretending there is teaches the wrong reflex.

## Related problems

Problem 872 is the same log with a min-heap and no tie rule. Problem 891 keeps a maximum too, but allows an arbitrary value to be removed, which a heap cannot do directly.

## Cost

Time O(q log q). Space O(q).

Constraints - `1 ≤ q ≤ 200000` - `0 ≤ p ≤ 1000000000` - `1 ≤ id ≤ 1000000000` - All identifiers in one log are distinct.