Hospital Triage
Hard · heap
A clinic has one waiting room and one doctor. You are given a list events describing what happens during the day, in order. Each event is a string in one of three forms:
"arrive <name> <severity>": a new patient joins the waiting room.severityis a whole number from 1 to 100, and a bigger number means a more urgent case. Two patients waiting at the same time never share a name."leave <name>": that patient gives up and goes home. If nobody with that name is waiting (they were already treated, already left, or never arrived), nothing happens."treat": the doctor calls in the waiting patient with the highest severity. If several waiting patients share the highest severity, the one who arrived earliest goes first. That patient is no longer waiting. If the waiting room is empty, nobody is called in.
Return a list with one entry for every "treat" event, in the order the events happen: the name of the patient who was called in, or "-" if the waiting room was empty.
A name can be used again after its owner has been treated or has left. The returning patient counts as a brand new arrival, with their own severity and their own place in the queue.
Examples
Example 1
Input: events = ["arrive ann 5", "arrive bo 9", "arrive cy 9", "treat", "treat", "treat", "treat"]
Output: ["bo", "cy", "ann", "-"]
bo and cy are both 9, and bo arrived first. ann goes last. The fourth treat finds an empty room.
Example 2
Input: events = ["arrive ann 4", "arrive bo 8", "leave bo", "leave dee", "treat"]
Output: ["ann"]
bo left before being treated, and dee was never waiting, so that event does nothing.
Example 3
Input: events = ["arrive ann 3", "arrive bo 3", "leave ann", "arrive ann 3", "treat", "treat"]
Output: ["bo", "ann"]
ann came back after leaving, so she is behind bo even though her first arrival was earlier.
Constraints
- 1 <= len(events) <= 10^4
- Every name is 1 to 10 lowercase letters or digits
- 1 <= severity <= 100
- An arrive event never uses a name that is currently waiting
- Each event is written exactly as in the three forms above, with single spaces