932. Priority Task Board

Medium3.5 points estimatedDesignHeapHash TableOrdered Set4 hints
RPby Rohit Parihar

A team keeps a to-do board. Each task has a unique taskId, an owner userId and an integer priority. Build TaskBoard; its constructor receives tasks, a list of [userId, taskId, priority] triples (possibly empty).

  • add(userId, taskId, priority) adds a task whose id has never been used.
  • edit(taskId, newPriority) changes the priority of an existing task.
  • rmv(taskId) deletes an existing task.
  • execTop() runs the task with the highest priority, breaking ties by the smaller taskId, deletes it and returns its userId; return -1 if the board is empty.

A task that was run or removed is gone and is never edited or removed again. Aim for O(log n) per call.

Example 1

Input:
operations = ["TaskBoard","execTop","add","edit","execTop","rmv","execTop","execTop","execTop"]arguments = [[[[11,301,8],[12,302,5],[13,303,8]]],[],[14,150,5],[302,9],[],[150],[],[],[]]
Output:
[null,11,null,null,12,null,13,-1,-1]
Explanation:

Tasks 301 and 303 tie at priority 8, so the smaller id 301 runs first and its user 11 is returned. Editing task 302 to 9 puts it on top (user 12). Task 150 (priority 5) is removed before it can run, so the next run returns user 13, and then the board is empty and execTop returns -1.

Example 2

Input:
operations = ["TaskBoard","execTop","add","execTop"]arguments = [[[]],[],[5,10,0],[]]
Output:
[null,-1,null,5]
Explanation:

Executing an empty board returns -1; a priority of 0 is still a valid priority.

Constraints

0 ≤ tasks.length ≤ 105; at most 2000 calls

1 ≤ userId, taskId ≤ 105; 0 ≤ priority, newPriority ≤ 109

edit and rmv only target tasks currently on the board

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) amortised per call
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.