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 Overview: Design a task manager that supports dynamic operations such as adding tasks, editing their priority, removing tasks, and executing the highest-priority task. The system must always return the task with the highest priority (with tie-breaking rules), while keeping updates efficient.
Approach 1: Linear Scan with Array/List (O(n) per query)
The simplest design stores every task in a list or array. Each task keeps fields such as taskId, userId, and priority. When the system needs to execute the highest-priority task, iterate through the entire list and select the best candidate based on priority and tie-breaking rules. Updating or removing tasks requires searching the list to locate the correct task first.
This approach is straightforward and useful for understanding the problem constraints. However, the cost becomes expensive as the number of tasks grows. Each query that needs the top task requires a full scan, giving O(n) time complexity per operation and O(n) space for storage. For systems with frequent updates and queries, this design quickly becomes a bottleneck.
Approach 2: Hash Map + Ordered Set (O(log n) operations)
A more scalable design combines a hash table with an ordered set. The hash map stores task metadata keyed by taskId, allowing O(1) lookups when editing or removing a task. The ordered set maintains tasks sorted by priority and tie-breaking rules (commonly (-priority, -taskId)) so the highest-priority task is always at the front.
When adding a task, insert it into both the hash map and the ordered structure. When editing a task's priority, remove the old entry from the ordered set, update the value, and reinsert it with the new priority. Removing a task deletes it from both structures. Executing the top task simply extracts the first element from the ordered set and removes it from the hash map.
The ordered structure can be implemented with a balanced tree or priority-based structure. Insertions, deletions, and reordering all cost O(log n), while the hash map keeps direct access to tasks for updates. Space complexity remains O(n) because each task is stored once in both structures. This pattern combines fast lookups with efficient ordering and appears frequently in system design-style problems and priority queue tasks.
Recommended for interviews: The Hash Map + Ordered Set design is the expected solution. Interviewers want to see that you separate concerns: use a hash map for direct task access and an ordered structure for efficient priority retrieval. Mentioning the naive scan approach shows understanding of the baseline, but implementing the ordered structure demonstrates stronger design skills.
We use a hash map d to store task information, where the key is the task ID and the value is a tuple (userId, priority) representing the user ID and the priority of the task.
We use an ordered set st to store all tasks currently in the system, where each element is a tuple (-priority, -taskId) representing the negative priority and negative task ID. We use negative values so that the task with the highest priority and largest task ID appears first in the ordered set.
For each operation, we can process as follows:
(userId, taskId, priority), add it to the hash map d and the ordered set st.(userId, taskId, priority) to the hash map d and the ordered set st.d, remove the old task information from the ordered set st, then add the new task information to both the hash map and the ordered set.d, remove the task information from the ordered set st, and delete the task from the hash map.st is empty, return -1. Otherwise, take the first element from the ordered set, get the task ID, retrieve the corresponding user ID from the hash map, and remove the task from both the hash map and the ordered set. Finally, return the user ID.For time complexity, initialization requires O(n log n) time, where n is the number of initial tasks. Each add, edit, remove, and execute operation requires O(log m) time, where m is the current number of tasks in the system. Since the total number of operations does not exceed 2 times 10^5, the overall time complexity is acceptable. The space complexity is O(n + m) for storing the hash map and ordered set.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan with List | O(n) per operation | O(n) | Good for small datasets or when simplicity matters more than performance |
| Hash Map + Ordered Set | O(log n) updates, O(log n) removal | O(n) | Best for dynamic systems with frequent inserts, updates, and priority queries |
Design Task Manager | Simple Intuition | Dry Run | Leetcode 3408 | codestorywithMIK • codestorywithMIK • 6,905 views views
Watch 9 more video solutions →Practice Design Task Manager with our built-in code editor and test cases.
Practice on FleetCode