Watch 10 video solutions for Design Task Manager, a medium level problem involving Hash Table, Design, Heap (Priority Queue). This walkthrough by codestorywithMIK has 6,905 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |