Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
There is a task management system that allows users to manage their tasks, each associated with a priority. The system should efficiently handle adding, modifying, executing, and removing tasks.
Implement the TaskManager class:
TaskManager(vector<vector<int>>& tasks) initializes the task manager with a list of user-task-priority triples. Each element in the input list is of the form [userId, taskId, priority], which adds a task to the specified user with the given priority.
void add(int userId, int taskId, int priority) adds a task with the specified taskId and priority to the user with userId. It is guaranteed that taskId does not exist in the system.
void edit(int taskId, int newPriority) updates the priority of the existing taskId to newPriority. It is guaranteed that taskId exists in the system.
void rmv(int taskId) removes the task identified by taskId from the system. It is guaranteed that taskId exists in the system.
int execTop() executes the task with the highest priority across all users. If there are multiple tasks with the same highest priority, execute the one with the highest taskId. After executing, the taskId is removed from the system. Return the userId associated with the executed task. If no tasks are available, return -1.
Note that a user may be assigned multiple tasks.
Example 1:
Input:
["TaskManager", "add", "edit", "execTop", "rmv", "add", "execTop"]
[[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]
Output:
[null, null, null, 3, null, null, 5]
Explanation
TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // Initializes with three tasks for Users 1, 2, and 3.Constraints:
1 <= tasks.length <= 1050 <= userId <= 1050 <= taskId <= 1050 <= priority <= 1090 <= newPriority <= 1092 * 105 calls will be made in total to add, edit, rmv, and execTop methods.taskId will be valid.Problem summary: There is a task management system that allows users to manage their tasks, each associated with a priority. The system should efficiently handle adding, modifying, executing, and removing tasks. Implement the TaskManager class: TaskManager(vector<vector<int>>& tasks) initializes the task manager with a list of user-task-priority triples. Each element in the input list is of the form [userId, taskId, priority], which adds a task to the specified user with the given priority. void add(int userId, int taskId, int priority) adds a task with the specified taskId and priority to the user with userId. It is guaranteed that taskId does not exist in the system. void edit(int taskId, int newPriority) updates the priority of the existing taskId to newPriority. It is guaranteed that taskId exists in the system. void rmv(int taskId) removes the task identified by taskId from the system. It is
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Design · Segment Tree
["TaskManager","add","edit","execTop","rmv","add","execTop"] [[[[1,101,10],[2,102,20],[3,103,15]]],[4,104,5],[102,8],[],[101],[5,105,15],[]]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3408: Design Task Manager
class TaskManager {
private final Map<Integer, int[]> d = new HashMap<>();
private final TreeSet<int[]> st = new TreeSet<>((a, b) -> {
if (a[0] == b[0]) {
return b[1] - a[1];
}
return b[0] - a[0];
});
public TaskManager(List<List<Integer>> tasks) {
for (var task : tasks) {
add(task.get(0), task.get(1), task.get(2));
}
}
public void add(int userId, int taskId, int priority) {
d.put(taskId, new int[] {userId, priority});
st.add(new int[] {priority, taskId});
}
public void edit(int taskId, int newPriority) {
var e = d.get(taskId);
int userId = e[0], priority = e[1];
st.remove(new int[] {priority, taskId});
st.add(new int[] {newPriority, taskId});
d.put(taskId, new int[] {userId, newPriority});
}
public void rmv(int taskId) {
var e = d.remove(taskId);
int priority = e[1];
st.remove(new int[] {priority, taskId});
}
public int execTop() {
if (st.isEmpty()) {
return -1;
}
var e = st.pollFirst();
var t = d.remove(e[1]);
return t[0];
}
}
/**
* Your TaskManager object will be instantiated and called as such:
* TaskManager obj = new TaskManager(tasks);
* obj.add(userId,taskId,priority);
* obj.edit(taskId,newPriority);
* obj.rmv(taskId);
* int param_4 = obj.execTop();
*/
// Accepted solution for LeetCode #3408: Design Task Manager
type TaskManager struct {
d map[int][2]int
st *redblacktree.Tree[int, int]
}
func encode(priority, taskId int) int {
return (priority << 32) | taskId
}
func comparator(a, b int) int {
if a > b {
return -1
} else if a < b {
return 1
}
return 0
}
func Constructor(tasks [][]int) TaskManager {
tm := TaskManager{
d: make(map[int][2]int),
st: redblacktree.NewWith[int, int](comparator),
}
for _, task := range tasks {
tm.Add(task[0], task[1], task[2])
}
return tm
}
func (this *TaskManager) Add(userId int, taskId int, priority int) {
this.d[taskId] = [2]int{userId, priority}
this.st.Put(encode(priority, taskId), taskId)
}
func (this *TaskManager) Edit(taskId int, newPriority int) {
if e, ok := this.d[taskId]; ok {
priority := e[1]
this.st.Remove(encode(priority, taskId))
this.d[taskId] = [2]int{e[0], newPriority}
this.st.Put(encode(newPriority, taskId), taskId)
}
}
func (this *TaskManager) Rmv(taskId int) {
if e, ok := this.d[taskId]; ok {
priority := e[1]
delete(this.d, taskId)
this.st.Remove(encode(priority, taskId))
}
}
func (this *TaskManager) ExecTop() int {
if this.st.Empty() {
return -1
}
it := this.st.Iterator()
it.Next()
taskId := it.Value()
if e, ok := this.d[taskId]; ok {
delete(this.d, taskId)
this.st.Remove(it.Key())
return e[0]
}
return -1
}
/**
* Your TaskManager object will be instantiated and called as such:
* obj := Constructor(tasks);
* obj.Add(userId,taskId,priority);
* obj.Edit(taskId,newPriority);
* obj.Rmv(taskId);
* param_4 := obj.ExecTop();
*/
# Accepted solution for LeetCode #3408: Design Task Manager
class TaskManager:
def __init__(self, tasks: List[List[int]]):
self.d = {}
self.st = SortedList()
for task in tasks:
self.add(*task)
def add(self, userId: int, taskId: int, priority: int) -> None:
self.d[taskId] = (userId, priority)
self.st.add((-priority, -taskId))
def edit(self, taskId: int, newPriority: int) -> None:
userId, priority = self.d[taskId]
self.st.discard((-priority, -taskId))
self.d[taskId] = (userId, newPriority)
self.st.add((-newPriority, -taskId))
def rmv(self, taskId: int) -> None:
_, priority = self.d[taskId]
self.d.pop(taskId)
self.st.remove((-priority, -taskId))
def execTop(self) -> int:
if not self.st:
return -1
taskId = -self.st.pop(0)[1]
userId, _ = self.d[taskId]
self.d.pop(taskId)
return userId
# Your TaskManager object will be instantiated and called as such:
# obj = TaskManager(tasks)
# obj.add(userId,taskId,priority)
# obj.edit(taskId,newPriority)
# obj.rmv(taskId)
# param_4 = obj.execTop()
// Accepted solution for LeetCode #3408: Design Task Manager
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3408: Design Task Manager
// class TaskManager {
// private final Map<Integer, int[]> d = new HashMap<>();
// private final TreeSet<int[]> st = new TreeSet<>((a, b) -> {
// if (a[0] == b[0]) {
// return b[1] - a[1];
// }
// return b[0] - a[0];
// });
//
// public TaskManager(List<List<Integer>> tasks) {
// for (var task : tasks) {
// add(task.get(0), task.get(1), task.get(2));
// }
// }
//
// public void add(int userId, int taskId, int priority) {
// d.put(taskId, new int[] {userId, priority});
// st.add(new int[] {priority, taskId});
// }
//
// public void edit(int taskId, int newPriority) {
// var e = d.get(taskId);
// int userId = e[0], priority = e[1];
// st.remove(new int[] {priority, taskId});
// st.add(new int[] {newPriority, taskId});
// d.put(taskId, new int[] {userId, newPriority});
// }
//
// public void rmv(int taskId) {
// var e = d.remove(taskId);
// int priority = e[1];
// st.remove(new int[] {priority, taskId});
// }
//
// public int execTop() {
// if (st.isEmpty()) {
// return -1;
// }
// var e = st.pollFirst();
// var t = d.remove(e[1]);
// return t[0];
// }
// }
//
// /**
// * Your TaskManager object will be instantiated and called as such:
// * TaskManager obj = new TaskManager(tasks);
// * obj.add(userId,taskId,priority);
// * obj.edit(taskId,newPriority);
// * obj.rmv(taskId);
// * int param_4 = obj.execTop();
// */
// Accepted solution for LeetCode #3408: Design Task Manager
class TaskManager {
private d: Map<number, [number, number]>;
private pq: PriorityQueue<[number, number]>;
constructor(tasks: number[][]) {
this.d = new Map();
this.pq = new PriorityQueue<[number, number]>((a, b) => {
if (a[0] === b[0]) {
return b[1] - a[1];
}
return b[0] - a[0];
});
for (const task of tasks) {
this.add(task[0], task[1], task[2]);
}
}
add(userId: number, taskId: number, priority: number): void {
this.d.set(taskId, [userId, priority]);
this.pq.enqueue([priority, taskId]);
}
edit(taskId: number, newPriority: number): void {
const e = this.d.get(taskId);
if (!e) return;
const userId = e[0];
this.d.set(taskId, [userId, newPriority]);
this.pq.enqueue([newPriority, taskId]);
}
rmv(taskId: number): void {
this.d.delete(taskId);
}
execTop(): number {
while (!this.pq.isEmpty()) {
const [priority, taskId] = this.pq.dequeue();
const e = this.d.get(taskId);
if (e && e[1] === priority) {
this.d.delete(taskId);
return e[0];
}
}
return -1;
}
}
/**
* Your TaskManager object will be instantiated and called as such:
* var obj = new TaskManager(tasks)
* obj.add(userId,taskId,priority)
* obj.edit(taskId,newPriority)
* obj.rmv(taskId)
* var param_4 = obj.execTop()
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.