Design Task Manager
Design Task Manager is a medium heaps problem solved with the composite comparator pattern.
The best approach, optimal (max-heap with lazy deletion), runs in O(log N) amortized per operation time and O(N) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan for the top) up.
Problem
Build a TaskManager that tracks tasks owned by users. Each task has a userId, a unique taskId and a priority. The constructor receives the initial tasks as triples [userId, taskId, priority].
Support four operations: add(userId, taskId, priority) inserts a new task; edit(taskId, newPriority) changes the priority of an existing task; rmv(taskId) deletes an existing task; and execTop() runs the task with the highest priority (on a tie, the one with the larger task id), removes it from the system and returns the userId that owned it. If no tasks are left, execTop() returns -1.
Examples
Example 1
- Input
TaskManager([[1, 10, 4], [2, 20, 9], [3, 30, 4]]), add(4, 40, 6), edit(20, 1), execTop(), rmv(10), execTop(), execTop()- Output
4, 3, 2- Why
- After the edit, task 40 (priority 6) is on top and belongs to user 4. Task 10 is removed, so task 30 (priority 4) runs next, then task 20 (priority 1).
Example 2
- Input
TaskManager([[5, 7, 3], [6, 8, 3]]), execTop(), execTop(), execTop()- Output
6, 5, -1- Why
- Both tasks have priority 3, so the larger task id 8 (user 6) runs first. Then nothing is left, giving -1.
Constraints
1 <= tasks.length <= 10^5, eachtasks[i] = [userId, taskId, priority]0 <= userId <= 10^5,0 <= taskId <= 10^5,0 <= priority <= 10^9- Task ids are unique among the tasks currently in the system.
addis only called with a task id that is not in the system;editandrmvonly with one that is.- At most
2 * 10^5calls in total toadd,edit,rmvandexecTop.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan for the top) | O(1) for add/edit/rmv, O(n) for execTop | O(n) |
| Optimal (max-heap with lazy deletion) | O(log N) amortized per operation | O(N) |
1Brute force (scan for the top)
O(1) for add/edit/rmv, O(n) for execTopexecTop looks at every stored task.O(n)One map entry per task in the system.Store tasks in a map from task id to (user id, priority). Every update is a direct map operation, and execTop scans all tasks to find the best one.
- Constructor: add every initial task to the map.
- add / edit / rmv: insert, update the priority, or delete in the map.
- execTop: scan all entries for the highest priority (larger task id on ties), delete it and return its user id; return -1 if the map is empty.
class TaskManager {
private final Map<Integer, int[]> info = new HashMap<>(); // taskId -> {userId, priority}
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) {
info.put(taskId, new int[] { userId, priority });
}
public void edit(int taskId, int newPriority) {
info.get(taskId)[1] = newPriority;
}
public void rmv(int taskId) {
info.remove(taskId);
}
public int execTop() {
int best = -1, bestPriority = -1;
for (Map.Entry<Integer, int[]> e : info.entrySet()) {
int id = e.getKey(), p = e.getValue()[1];
if (p > bestPriority || (p == bestPriority && id > best)) {
best = id;
bestPriority = p;
}
}
if (best == -1) return -1;
return info.remove(best)[0];
}
}class TaskManager:
def __init__(self, tasks: List[List[int]]):
self.info = {} # taskId -> [userId, priority]
for user_id, task_id, priority in tasks:
self.add(user_id, task_id, priority)
def add(self, userId: int, taskId: int, priority: int) -> None:
self.info[taskId] = [userId, priority]
def edit(self, taskId: int, newPriority: int) -> None:
self.info[taskId][1] = newPriority
def rmv(self, taskId: int) -> None:
del self.info[taskId]
def execTop(self) -> int:
best, best_priority = -1, -1
for task_id, (_, p) in self.info.items():
if p > best_priority or (p == best_priority and task_id > best):
best, best_priority = task_id, p
if best == -1:
return -1
return self.info.pop(best)[0]class TaskManager {
unordered_map<int, pair<int, int>> info; // taskId -> {userId, priority}
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) {
info[taskId] = {userId, priority};
}
void edit(int taskId, int newPriority) {
info[taskId].second = newPriority;
}
void rmv(int taskId) {
info.erase(taskId);
}
int execTop() {
int best = -1, bestPriority = -1;
for (auto& e : info) {
int id = e.first, p = e.second.second;
if (p > bestPriority || (p == bestPriority && id > best)) {
best = id;
bestPriority = p;
}
}
if (best == -1) return -1;
int user = info[best].first;
info.erase(best);
return user;
}
};class TaskManager {
constructor(tasks) {
this.info = new Map(); // taskId -> [userId, priority]
for (const [userId, taskId, priority] of tasks) this.add(userId, taskId, priority);
}
add(userId, taskId, priority) {
this.info.set(taskId, [userId, priority]);
}
edit(taskId, newPriority) {
this.info.get(taskId)[1] = newPriority;
}
rmv(taskId) {
this.info.delete(taskId);
}
execTop() {
let best = -1, bestPriority = -1;
for (const [id, [, p]] of this.info) {
if (p > bestPriority || (p === bestPriority && id > best)) {
best = id;
bestPriority = p;
}
}
if (best === -1) return -1;
const user = this.info.get(best)[0];
this.info.delete(best);
return user;
}
}2Optimal (max-heap with lazy deletion)
O(log N) amortized per operationEach snapshot is pushed once and popped at most once, and every push or pop costs O(log N), where N is the number of snapshots ever pushed.O(N)The map holds the live tasks and the heap holds at most one snapshot per add or edit.Keep the same map as the source of truth, plus a max-heap of (priority, taskId) snapshots. add and edit push a new snapshot; nothing is ever deleted from the heap directly. In execTop, pop snapshots until one still matches the map (the task exists and its current priority equals the snapshot's); that is the real top task.
- add: store taskId -> (userId, priority) and push (priority, taskId).
- edit: update the priority in the map and push (newPriority, taskId); the old snapshot becomes stale.
- rmv: delete the task from the map only; its snapshots become stale.
- execTop: pop the heap; skip a snapshot if the task is missing or its priority differs. On the first valid one, delete the task from the map and return its user id. If the heap empties, return -1.
class TaskManager {
private final Map<Integer, int[]> info = new HashMap<>(); // taskId -> {userId, priority}
private final PriorityQueue<int[]> heap = new PriorityQueue<>(
(a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(b[1], a[1]));
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) {
info.put(taskId, new int[] { userId, priority });
heap.offer(new int[] { priority, taskId });
}
public void edit(int taskId, int newPriority) {
info.get(taskId)[1] = newPriority;
heap.offer(new int[] { newPriority, taskId });
}
public void rmv(int taskId) {
info.remove(taskId);
}
public int execTop() {
while (!heap.isEmpty()) {
int[] top = heap.poll();
int[] cur = info.get(top[1]);
if (cur != null && cur[1] == top[0]) {
info.remove(top[1]);
return cur[0];
}
}
return -1;
}
}class TaskManager:
def __init__(self, tasks: List[List[int]]):
self.info = {} # taskId -> [userId, priority]
self.heap = [] # (-priority, -taskId)
for user_id, task_id, priority in tasks:
self.add(user_id, task_id, priority)
def add(self, userId: int, taskId: int, priority: int) -> None:
self.info[taskId] = [userId, priority]
heapq.heappush(self.heap, (-priority, -taskId))
def edit(self, taskId: int, newPriority: int) -> None:
self.info[taskId][1] = newPriority
heapq.heappush(self.heap, (-newPriority, -taskId))
def rmv(self, taskId: int) -> None:
del self.info[taskId]
def execTop(self) -> int:
while self.heap:
neg_p, neg_id = heapq.heappop(self.heap)
cur = self.info.get(-neg_id)
if cur is not None and cur[1] == -neg_p:
del self.info[-neg_id]
return cur[0]
return -1class TaskManager {
unordered_map<int, pair<int, int>> info; // taskId -> {userId, priority}
priority_queue<pair<int, int>> heap; // (priority, taskId), max first
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) {
info[taskId] = {userId, priority};
heap.push({priority, taskId});
}
void edit(int taskId, int newPriority) {
info[taskId].second = newPriority;
heap.push({newPriority, taskId});
}
void rmv(int taskId) {
info.erase(taskId);
}
int execTop() {
while (!heap.empty()) {
auto [p, id] = heap.top();
heap.pop();
auto it = info.find(id);
if (it != info.end() && it->second.second == p) {
int user = it->second.first;
info.erase(it);
return user;
}
}
return -1;
}
};class TaskManager {
constructor(tasks) {
this.info = new Map(); // taskId -> [userId, priority]
this.heap = []; // [priority, taskId], max first
for (const [userId, taskId, priority] of tasks) this.add(userId, taskId, priority);
}
static higher(a, b) {
return a[0] !== b[0] ? a[0] > b[0] : a[1] > b[1];
}
push(item) {
const h = this.heap;
h.push(item);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!TaskManager.higher(h[i], h[p])) break;
[h[i], h[p]] = [h[p], h[i]];
i = p;
}
}
pop() {
const h = this.heap;
const top = h[0];
const last = h.pop();
if (h.length > 0) {
h[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let best = i;
if (l < h.length && TaskManager.higher(h[l], h[best])) best = l;
if (r < h.length && TaskManager.higher(h[r], h[best])) best = r;
if (best === i) break;
[h[i], h[best]] = [h[best], h[i]];
i = best;
}
}
return top;
}
add(userId, taskId, priority) {
this.info.set(taskId, [userId, priority]);
this.push([priority, taskId]);
}
edit(taskId, newPriority) {
this.info.get(taskId)[1] = newPriority;
this.push([newPriority, taskId]);
}
rmv(taskId) {
this.info.delete(taskId);
}
execTop() {
while (this.heap.length > 0) {
const [p, id] = this.pop();
const cur = this.info.get(id);
if (cur !== undefined && cur[1] === p) {
this.info.delete(id);
return cur[0];
}
}
return -1;
}
}Edge cases to test
- Ties in priority, broken by the larger task id
execTopon an empty system returns -1- Editing a task several times, or editing it back to an older priority
- Removing a task and later adding a task with the same id again
- Priority 0 and priority 10^9
Hints
Hint 1
Keep a map from task id to (user id, current priority) so add, edit and rmv are O(1). The hard part is finding the top task fast.
Hint 2
A max-heap ordered by (priority, task id) finds the top quickly, but editing or removing an entry in the middle of a heap is awkward.
Hint 3
Lazy deletion: never delete from the heap. Push a fresh entry on every add or edit, and when popping, discard entries whose task is gone or whose priority no longer matches the map.
FAQ
What is the best time complexity for Design Task Manager?
Optimal (max-heap with lazy deletion) runs in O(log N) amortized per operation time and O(N) extra space. Each snapshot is pushed once and popped at most once, and every push or pop costs O(log N), where N is the number of snapshots ever pushed.
Which pattern does Design Task Manager use?
It is a heaps problem that uses the composite comparator pattern. Other problems with the same pattern: Top K Frequent Elements, Rank Teams by Votes, Design Movie Rental System.
Is there a brute force solution for Design Task Manager?
Yes. Brute force (scan for the top) takes O(1) for add/edit/rmv, O(n) for execTop time and O(n) space. Store tasks in a map from task id to (user id, priority).
Which edge cases should I test for Design Task Manager?
Ties in priority, broken by the larger task id; execTop on an empty system returns -1; Editing a task several times, or editing it back to an older priority; Removing a task and later adding a task with the same id again; Priority 0 and priority 10^9.