Design Task Manager
Problem
Implement a TaskManager seeded with [userId, taskId, priority] triples. Support add(userId, taskId, priority), edit(taskId, newPriority), rmv(taskId), and execTop(). execTop() runs the task with the highest priority; ties are broken by the highest taskId. It removes that task and returns its userId, or -1 if the system is empty.
init [[1,101,10],[2,102,20],[3,103,15]]; add(4,104,5); edit(102,8); execTop()3class TaskManager:
def __init__(self, tasks):
self.task = {} # taskId -> (userId, priority)
self.heap = [] # max-heap of (-priority, -taskId, taskId)
for userId, taskId, priority in tasks:
self.add(userId, taskId, priority)
def add(self, userId, taskId, priority):
self.task[taskId] = (userId, priority)
heapq.heappush(self.heap, (-priority, -taskId, taskId))
def edit(self, taskId, newPriority):
userId, _ = self.task[taskId]
self.task[taskId] = (userId, newPriority)
heapq.heappush(self.heap, (-newPriority, -taskId, taskId))
def rmv(self, taskId):
del self.task[taskId] # lazy: stale heap entry skipped later
def execTop(self):
while self.heap:
negp, _, taskId = self.heap[0]
cur = self.task.get(taskId)
if cur is not None and cur[1] == -negp: # entry still current
heapq.heappop(self.heap)
del self.task[taskId]
return cur[0]
heapq.heappop(self.heap) # drop stale entry
return -1class TaskManager {
constructor(tasks) {
this.task = new Map(); // taskId -> [userId, priority]
this.heap = new MaxHeap(); // ordered by (priority, taskId)
for (const [userId, taskId, priority] of tasks)
this.add(userId, taskId, priority);
}
add(userId, taskId, priority) {
this.task.set(taskId, [userId, priority]);
this.heap.push([priority, taskId]);
}
edit(taskId, newPriority) {
const [userId] = this.task.get(taskId);
this.task.set(taskId, [userId, newPriority]);
this.heap.push([newPriority, taskId]);
}
rmv(taskId) {
this.task.delete(taskId); // lazy: stale heap entry skipped later
}
execTop() {
while (this.heap.size() > 0) {
const [priority, taskId] = this.heap.peek();
const cur = this.task.get(taskId);
if (cur && cur[1] === priority) { // entry still current
this.heap.pop();
this.task.delete(taskId);
return cur[0];
}
this.heap.pop(); // drop stale entry
}
return -1;
}
}class TaskManager {
private Map<Integer, int[]> task = new HashMap<>(); // taskId -> {userId, priority}
// max-heap by priority, then taskId
private PriorityQueue<int[]> heap = new PriorityQueue<>(
(a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]); // {priority, taskId}
public TaskManager(List<List<Integer>> tasks) {
for (List<Integer> t : tasks) add(t.get(0), t.get(1), t.get(2));
}
public void add(int userId, int taskId, int priority) {
task.put(taskId, new int[]{userId, priority});
heap.offer(new int[]{priority, taskId});
}
public void edit(int taskId, int newPriority) {
int userId = task.get(taskId)[0];
task.put(taskId, new int[]{userId, newPriority});
heap.offer(new int[]{newPriority, taskId});
}
public void rmv(int taskId) {
task.remove(taskId); // lazy: stale heap entry skipped later
}
public int execTop() {
while (!heap.isEmpty()) {
int[] top = heap.peek();
int[] cur = task.get(top[1]);
if (cur != null && cur[1] == top[0]) { // entry still current
heap.poll();
task.remove(top[1]);
return cur[0];
}
heap.poll(); // drop stale entry
}
return -1;
}
}class TaskManager {
unordered_map<int, pair<int,int>> task; // taskId -> {userId, priority}
// max-heap of {priority, taskId}: bigger priority, then bigger taskId, wins
priority_queue<pair<int,int>> heap;
public:
TaskManager(vector<vector<int>>& tasks) {
for (auto& t : tasks) add(t[0], t[1], t[2]);
}
void add(int userId, int taskId, int priority) {
task[taskId] = {userId, priority};
heap.push({priority, taskId});
}
void edit(int taskId, int newPriority) {
int userId = task[taskId].first;
task[taskId] = {userId, newPriority};
heap.push({newPriority, taskId});
}
void rmv(int taskId) {
task.erase(taskId); // lazy: stale heap entry skipped later
}
int execTop() {
while (!heap.empty()) {
auto [priority, taskId] = heap.top();
auto it = task.find(taskId);
if (it != task.end() && it->second.second == priority) { // current
heap.pop();
int userId = it->second.first;
task.erase(it);
return userId;
}
heap.pop(); // drop stale entry
}
return -1;
}
};Explanation
The challenge is that execTop() must instantly find the globally highest-priority task, while edit and rmv can change or delete arbitrary tasks at any time. We pair two structures: a hash map for the truth about each task, and a max-heap for fast access to the best candidate.
The map task stores taskId → (userId, priority) and is the single source of truth. add writes a new entry, edit overwrites the priority, and rmv deletes the key. Every one of these is O(1).
The heap is ordered so the largest priority sits on top, and ties go to the largest taskId — exactly the order execTop needs. But a heap cannot cheaply update or delete an interior element, so instead of editing it we use lazy deletion: edit just pushes a fresh (newPriority, taskId) entry, and rmv leaves the old entry behind.
That means the heap can hold stale entries. execTop peeks the top and validates it against the map: the entry is current only if taskId still exists and its stored priority equals the entry's priority. If it matches, we pop, delete the task, and return its userId. If not, we pop the stale entry and look again.
Example: starting from {101:10, 102:20, 103:15}, after add(4,104,5) and edit(102,8) the priorities are 101→10, 102→8, 103→15, 104→5. The heap top might be the stale (20,102) entry, which fails validation and is discarded; the next valid top is (15,103), so execTop returns user 3.