Jukebox That Plays the Most-Requested Song First

A bar's jukebox takes song requests from customers' phones. When the current song ends, the jukebox picks the next song this way:

• Choose the song with the most pending requests.
• If several songs tie, choose the one whose latest pending request is the most recent.
• Playing a song uses up only one request for it, the most recent one. The rest stay pending.

Implement the class:

class Jukebox:
    def request(self, song: str) -> None: ...
    def play_next(self) -> str: ...   # never called when nothing is pending

Also write a small driver, run(log: list[str]) -> list[str]. Each entry in log is either a song name (a request) or the literal string "PLAY". The driver returns the songs played, in order.

Examples

log = ["lofi", "jazz", "lofi", "rock", "jazz",
       "PLAY", "PLAY", "PLAY", "PLAY", "PLAY"]
out = ["jazz", "lofi", "rock", "jazz", "lofi"]

• Pending: lofi x2, jazz x2, rock x1. lofi and jazz tie at 2, and jazz's latest request (5th) is newer than lofi's (3rd). Play jazz.
• Now lofi is the only song with 2. Play lofi.
• Every song now has 1 pending request. The newest still-pending one is rock (4th). Play rock. Then jazz (2nd), then lofi (1st).

log = ["a", "b", "b", "PLAY", "a", "PLAY", "PLAY", "c", "PLAY"]
out = ["b", "a", "b", "c"]

Constraints

• Up to 2 * 10^5 operations in total.
• play_next and request should each run in O(1) time (amortized is fine).
• Song names are arbitrary non-empty strings, never equal to "PLAY".