Design Task Manager - Video Solutions
Design Task Manager | Simple Intuition | Dry Run | Leetcode 3408 | codestorywithMIK
Design Task Manager - Video Solution
Watch 10 video solutions for Design Task Manager, a medium level problem involving Hash Table, Design, Heap (Priority Queue). This walkthrough by codestorywithMIK has 7,090 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 specifiedtaskIdandpriorityto the user withuserId. It is guaranteed thattaskIddoes not exist in the system. -
void edit(int taskId, int newPriority)updates the priority of the existingtaskIdtonewPriority. It is guaranteed thattaskIdexists in the system. -
void rmv(int taskId)removes the task identified bytaskIdfrom the system. It is guaranteed thattaskIdexists 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 highesttaskId. After executing, thetaskIdis removed from the system. Return theuserIdassociated 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.taskManager.add(4, 104, 5); // Adds task 104 with priority 5 for User 4.
taskManager.edit(102, 8); // Updates priority of task 102 to 8.
taskManager.execTop(); // return 3. Executes task 103 for User 3.
taskManager.rmv(101); // Removes task 101 from the system.
taskManager.add(5, 105, 15); // Adds task 105 with priority 15 for User 5.
taskManager.execTop(); // return 5. Executes task 105 for User 5.
Constraints:
1 <= tasks.length <= 1050 <= userId <= 1050 <= taskId <= 1050 <= priority <= 1090 <= newPriority <= 109- At most
2 * 105calls will be made in total toadd,edit,rmv, andexecTopmethods. - The input is generated such that
taskIdwill be valid.
Approach Overview
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.
Complexity Analysis
| 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 |