# Design Task Manager
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-task-manager)
Canonical: https://scaleengineer.com/dsa/problems/design-task-manager
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Hash Table, Heap (Priority Queue), Ordered Set
---
## Problem
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.  
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 <= 105`
* `0 <= userId <= 105`
* `0 <= taskId <= 105`
* `0 <= priority <= 109`
* `0 <= newPriority <= 109`
* At most `2 * 105` calls will be made in **total** to `add`, `edit`, `rmv`, and `execTop` methods.
* The input is generated such that `taskId` will be valid.

# Approaches
## Brute Force with HashMap (Linear Scan)
This approach uses a simple `HashMap` to store the tasks. While operations like adding, editing, and removing tasks are very fast (constant time), finding the task with the highest priority requires scanning through all the tasks currently in the system. This makes the `execTop` operation inefficient for a large number of tasks.
**Time:** - `add`, `edit`, `rmv`: `O(1)` on average.
- `execTop`: `O(N)`, where N is the number of tasks. This is because we must iterate through all tasks to find the maximum. · **Space:** O(N), where N is the number of tasks in the system. The `HashMap` stores an entry for each task.
**Pros:** Simple to understand and implement.; Extremely fast `O(1)` time complexity for `add`, `edit`, and `rmv` operations.
**Cons:** The `execTop` method is very inefficient with a time complexity of `O(N)`, where `N` is the number of tasks. This will lead to a 'Time Limit Exceeded' error on large test cases.
### Explanation
### Data Structure
The core of this approach is a `java.util.HashMap` that maps each `taskId` to an integer array containing its `userId` and `priority`. This provides `O(1)` average-case time complexity for lookups, insertions, and deletions by `taskId`.

### Method Implementations
- **`add`, `edit`, `rmv`**: These methods directly translate to the `HashMap`'s `put`, `get`/`put`, and `remove` operations, respectively. Since `taskId` is guaranteed to exist for `edit` and `rmv`, these operations are straightforward and efficient.
- **`execTop`**: This is the performance bottleneck. To find the highest priority task, we have no choice but to perform a full linear scan of all the values in the `HashMap`. We iterate through each task, keeping track of the one with the highest priority seen so far. If two tasks have the same priority, the one with the larger `taskId` is chosen. Once the entire map has been traversed, the winning task is removed from the map, and its `userId` is returned.

```java
import java.util.HashMap;
import java.util.Map;

class TaskManager {
    private Map<Integer, int[]> taskMap; // taskId -> {userId, priority}

    public TaskManager(int[][] tasks) {
        taskMap = new HashMap<>();
        for (int[] task : tasks) {
            add(task[0], task[1], task[2]);
        }
    }

    public void add(int userId, int taskId, int priority) {
        taskMap.put(taskId, new int[]{userId, priority});
    }

    public void edit(int taskId, int newPriority) {
        // The problem guarantees taskId exists.
        taskMap.get(taskId)[1] = newPriority;
    }

    public void rmv(int taskId) {
        taskMap.remove(taskId);
    }

    public int execTop() {
        if (taskMap.isEmpty()) {
            return -1;
        }

        int bestTaskId = -1;
        int maxPriority = -1;
        int bestUserId = -1;

        for (Map.Entry<Integer, int[]> entry : taskMap.entrySet()) {
            int currentTaskId = entry.getKey();
            int[] taskDetails = entry.getValue();
            int currentPriority = taskDetails[1];

            if (currentPriority > maxPriority) {
                maxPriority = currentPriority;
                bestTaskId = currentTaskId;
                bestUserId = taskDetails[0];
            } else if (currentPriority == maxPriority) {
                if (currentTaskId > bestTaskId) {
                    bestTaskId = currentTaskId;
                    bestUserId = taskDetails[0];
                }
            }
        }

        taskMap.remove(bestTaskId);
        return bestUserId;
    }
}
```
### Algorithm
- **Data Structure**: Use a `HashMap<Integer, int[]>` where the key is `taskId` and the value is an array `[userId, priority]`.
- **Initialization**: In the constructor, iterate through the initial list of tasks and populate the `HashMap`.
- **`add(userId, taskId, priority)`**: Insert a new entry into the `HashMap`. This is an `O(1)` operation.
- **`edit(taskId, newPriority)`**: Access the task by its `taskId` in the `HashMap` and update its priority value. This is an `O(1)` operation.
- **`rmv(taskId)`**: Remove the entry corresponding to `taskId` from the `HashMap`. This is an `O(1)` operation.
- **`execTop()`**: 
  - If the map is empty, return -1.
  - Initialize variables to track the best task found so far (e.g., `maxPriority`, `bestTaskId`, `bestUserId`).
  - Iterate through every task in the `HashMap`.
  - For each task, compare its priority (and `taskId` for tie-breaking) with the current best task.
  - If the current task is better, update the tracking variables.
  - After checking all tasks, the best task has been identified. Remove it from the `HashMap` and return its `userId`.

## Optimized Approach using Max-Heap and Lazy Deletion
This optimized approach uses a combination of a Max-Heap (implemented as a `PriorityQueue`) and a `HashMap` to achieve much better performance for the `execTop` operation. The `PriorityQueue` keeps tasks ordered by priority, allowing for logarithmic time access to the top task. To handle `edit` and `rmv` operations efficiently without incurring the high cost of modifying an arbitrary element in a heap, a 'lazy deletion' strategy is employed.
**Time:** - Let M be the total number of `add` and `edit` calls made.
- `add`, `edit`: `O(log M)` due to insertion into the priority queue.
- `rmv`: `O(1)` as it only involves a hash map removal.
- `execTop`: Amortized `O(log M)`. While a single call might remove multiple stale entries, each task version is pushed and popped from the heap only once over the entire sequence of operations. · **Space:** O(N + M), where N is the number of active tasks and M is the total number of `add` and `edit` operations. The `HashMap` takes `O(N)` space, and the `PriorityQueue` can take up to `O(M)` space due to stale entries.
**Pros:** Highly efficient `execTop` operation with logarithmic time complexity.; All operations (`add`, `edit`, `rmv`, `execTop`) have efficient time complexities suitable for large-scale problems.
**Cons:** More complex to implement due to the need to manage two data structures and handle stale entries.; Uses more memory than the brute-force approach because the `PriorityQueue` can temporarily store stale entries for tasks that have been edited or removed.
### Explanation
### Data Structures and Strategy
We use two main data structures:
1.  **`PriorityQueue<int[]>`**: A max-heap that stores task information as `[priority, taskId, userId]`. The custom comparator ensures that elements with higher priority are at the top. For ties in priority, the element with the higher `taskId` takes precedence. This makes finding the best task an `O(log M)` operation.
2.  **`HashMap<Integer, int[]>`**: This map stores the ground truth for each task, mapping a `taskId` to its `[userId, priority]`. It allows for `O(1)` updates and lookups.

The key idea is **lazy deletion**. When a task is edited or removed, we don't try to find and remove the old entry from the heap (which is an `O(M)` operation). Instead, we mark it as invalid by either updating (`edit`) or removing (`rmv`) its entry in the `HashMap`. The `execTop` method is then responsible for filtering out these 'stale' tasks from the top of the heap before executing a valid one.

### Method Implementations
- **`add`**: A new task is added to both the `HashMap` and the `PriorityQueue`.
- **`edit`**: The task's priority is updated in the `HashMap`. A new entry representing the updated task is added to the `PriorityQueue`. The old entry is now stale.
- **`rmv`**: The task is removed from the `HashMap`. Its entry in the `PriorityQueue` is now stale.
- **`execTop`**: We peek at the top of the `PriorityQueue`. We check its validity against the `HashMap`. If the task doesn't exist in the map or its priority is outdated, we `poll` it and check the next one. This continues until a valid task is found at the top. This valid task is then removed from both data structures, and its `userId` is returned.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class TaskManager {
    // Max-heap to get the top task efficiently. Stores {priority, taskId, userId}
    private PriorityQueue<int[]> pq;
    // Map to store the current valid state of a task. taskId -> {userId, priority}
    private Map<Integer, int[]> taskMap;

    public TaskManager(int[][] tasks) {
        // Comparator for the max-heap:
        // 1. Higher priority first.
        // 2. If priorities are equal, higher taskId first.
        pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return b[0] - a[0]; // Descending priority
            }
            return b[1] - a[1]; // Descending taskId
        });

        taskMap = new HashMap<>();
        for (int[] task : tasks) {
            add(task[0], task[1], task[2]);
        }
    }

    public void add(int userId, int taskId, int priority) {
        taskMap.put(taskId, new int[]{userId, priority});
        pq.offer(new int[]{priority, taskId, userId});
    }

    public void edit(int taskId, int newPriority) {
        int[] taskDetails = taskMap.get(taskId);
        taskDetails[1] = newPriority;
        // No need for taskMap.put() as the array is modified by reference
        
        // Add the new version of the task to the priority queue.
        // The old version is now "stale" and will be ignored by execTop.
        pq.offer(new int[]{newPriority, taskId, taskDetails[0]});
    }

    public void rmv(int taskId) {
        // Simply remove from the map. The entry in the PQ becomes "stale".
        taskMap.remove(taskId);
    }

    public int execTop() {
        // Clean up stale tasks from the top of the queue
        while (!pq.isEmpty()) {
            int[] topTask = pq.peek();
            int priority = topTask[0];
            int taskId = topTask[1];

            // A task is valid if it exists in the map and its priority matches.
            if (taskMap.containsKey(taskId) && taskMap.get(taskId)[1] == priority) {
                // Valid task found, execute it
                pq.poll(); // Remove from pq
                taskMap.remove(taskId); // Remove from map
                return topTask[2]; // Return userId
            } else {
                // This is a stale task (either removed or edited), discard it.
                pq.poll();
            }
        }
        // No valid tasks left
        return -1;
    }
}
```
### Algorithm
- **Data Structures**:
  - A `PriorityQueue<int[]>` (Max-Heap) to store tasks as `[priority, taskId, userId]`. It's ordered by priority, then `taskId`, to make finding the top task efficient.
  - A `HashMap<Integer, int[]>` to map `taskId` to `[userId, priority]`. This map serves as the single source of truth for a task's current state.
- **`add(userId, taskId, priority)`**: Add the task to both the `HashMap` and the `PriorityQueue`.
- **`edit(taskId, newPriority)`**: Update the task's priority in the `HashMap`. Then, add a *new* entry for this task with the updated priority to the `PriorityQueue`. The old entry in the queue is not removed; it becomes 'stale'.
- **`rmv(taskId)`**: Remove the task from the `HashMap`. The corresponding entry in the `PriorityQueue` becomes 'stale'.
- **`execTop()`**: 
  - Repeatedly look at the top element of the `PriorityQueue`.
  - Check if this task is 'stale' by comparing it with the information in the `HashMap`. A task is stale if it's not in the map, or if its priority in the queue doesn't match the current priority in the map.
  - If the top task is stale, remove it from the queue and repeat.
  - If the top task is valid, it's the one to be executed. Remove it from both the queue and the map, and return its `userId`.

# Solutions
### Java

```java
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(); */
```

### CPP

```cpp
class TaskManager { private: unordered_map < int , pair < int , int >> d ; set < pair < int , int >> st ; public: TaskManager ( vector < vector < int >>& tasks ) { for ( const auto & task : tasks ) { add ( task [ 0 ], task [ 1 ], task [ 2 ]); } } void add ( int userId , int taskId , int priority ) { d [ taskId ] = { userId , priority }; st . insert ({ - priority , - taskId }); } void edit ( int taskId , int newPriority ) { auto [ userId , priority ] = d [ taskId ]; st . erase ({ - priority , - taskId }); st . insert ({ - newPriority , - taskId }); d [ taskId ] = { userId , newPriority }; } void rmv ( int taskId ) { auto [ userId , priority ] = d [ taskId ]; st . erase ({ - priority , - taskId }); d . erase ( taskId ); } int execTop () { if ( st . empty ()) { return - 1 ; } auto e = * st . begin (); st . erase ( st . begin ()); int taskId = - e . second ; int userId = d [ taskId ]. first ; d . erase ( taskId ); return userId ; } }; /** * 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(); */
```

### Python

```python
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()
```