#221MediumDesign· Priority Queue with Lazy Deletion

Cancellable Task Queue

A print server receives jobs from many users. Each job has an integer `taskId` and a priority; the server always prints the waiting job with the highest priority next. Users can also cancel a job that is still waiting, and a job that is resubmitted with the same id replaces the waiting one with the new priority. Design a class `CancellableTaskQueue`: - `CancellableTaskQueue()` creates an empty queue. - `add(taskId, priority)` puts the task in the queue. If a task with this id is already waiting, its priority is replaced by the new one (the task stays a single entry). - `cancel(taskId)` removes the waiting task with this id. It returns `true` if such a task was waiting and `false` otherwise. - `popNext()` removes and returns the id of the waiting task with the highest priority. If several tasks share the highest priority, the one with the smallest `taskId` goes first. If the queue is empty it returns `-1`. Every operation should run in O(log n) amortised time. Scanning the whole queue for each call is too slow.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor and for `add`, a boolean for `cancel`, and the task id (or -1) for `popNext`.

Examples

Input: operations = ["CancellableTaskQueue", "add", "add", "add", "popNext", "cancel", "popNext", "popNext"], arguments = [[], [1, 5], [2, 9], [3, 9], [], [3], [], []]

Output: [null, null, null, null, 2, true, 1, -1]

Tasks 2 and 3 share the highest priority 9, so the smaller id 2 is printed first. Task 3 is then cancelled, which leaves only task 1.

Input: operations = ["CancellableTaskQueue", "add", "add", "add", "popNext", "popNext"], arguments = [[], [7, 1], [8, 4], [7, 10], [], []]

Output: [null, null, null, null, 7, 8]

Adding task 7 again replaces its priority 1 by 10, so it overtakes task 8. The queue never holds two entries for id 7.

Input: operations = ["CancellableTaskQueue", "popNext", "cancel", "add", "cancel", "cancel"], arguments = [[], [], [4], [4, 2], [4], [4]]

Output: [null, -1, false, null, true, false]

Popping an empty queue gives -1 and cancelling an unknown id gives false. After the add the first cancel succeeds, the second one finds nothing.

Constraints

0 <= taskId <= 10^9
-10^9 <= priority <= 10^9
At most 10^5 calls in total

#heap
#priority-queue
#lazy-deletion
#design
#hash-table