Beats 100% | Simplified Approach | Easy Explanation | TC O(n) | C++ | Java |
IntuitionThe problem revolves around efficiently managing tasks with priorities while supporting operations like adding, editing, removing, and executing tasks

# Intuition
The problem revolves around efficiently managing tasks with priorities while supporting operations like adding, editing, removing, and executing tasks with the highest priority. A natural choice for such a problem is a **priority queue** (max-heap) to keep track of the tasks based on their priorities, and an **unordered map** to store task details for quick lookups and updates.

---

# Approach
1. **Data Structures**:
   - A `priority_queue` is used to store tasks in the form of vectors `{priority, taskId, userId}`. The priority queue ensures that the task with the highest priority is always at the top.
   - An `unordered_map` is used to map each `taskId` to its `{priority, userId}` pair, allowing for constant-time lookups and updates.

2. **Initialization**:
   - During initialization, all tasks are added to the `priority_queue` and `unordered_map`. This ensures that the system is ready to handle all operations efficiently.

3. **Operations**:
   - **`add(userId, taskId, priority)`**:
     - Add a new task to both the `priority_queue` and the `unordered_map`.
   - **`edit(taskId, newPriority)`**:
     - Update the task's priority in the `unordered_map`.
     - Push the updated task into the `priority_queue` without removing the old instance. This is a lazy update approach where outdated tasks are ignored during execution.
   - **`rmv(taskId)`**:
     - Remove the task from the `unordered_map`. The outdated task in the `priority_queue` will be ignored during execution.
   - **`execTop()`**:
     - Continuously check the top of the `priority_queue`. If the task is valid (exists in the `unordered_map` and matches the stored priority), remove it from both the `priority_queue` and `unordered_map` and return the `userId`. Otherwise, discard the outdated task and continue.

4. **Lazy Deletion**:
   - Instead of directly removing tasks from the `priority_queue`, which is not feasible, the solution relies on a lazy deletion approach. Invalid tasks are ignored during execution, ensuring efficient operations.

---

# Complexity

- **Time Complexity**:
  - **Initialization**: $$O(n \log n)$$, where $$n$$ is the number of tasks. Each task insertion into the `priority_queue` takes $$O(\log n)$$.
  - **`add`**: $$O(\log n)$$ for insertion into the `priority_queue` and $$O(1)$$ for insertion into the `unordered_map`.
  - **`edit`**: $$O(\log n)$$ for insertion into the `priority_queue` and $$O(1)$$ for updating the `unordered_map`.
  - **`rmv`**: $$O(1)$$ for removing a task from the `unordered_map`.
  - **`execTop`**: $$O(\log n)$$ in the worst case for removing outdated tasks from the `priority_queue`.

- **Space Complexity**:
  - $$O(n)$$ for storing tasks in the `priority_queue` and $$O(n)$$ for the `unordered_map`.

---

This solution is efficient and leverages the strengths of the `priority_queue` and `unordered_map` to handle the constraints of the problem effectively.


# Code
```cpp []
class TaskManager {
    priority_queue<vector<int>> q;
    unordered_map<int, vector<int>> taskMap;
public:
    TaskManager(vector<vector<int>>& tasks) {
        for(int i=0;i<tasks.size();i++)
            {
                // q.push({tasks[i][2],tasks[i][1],tasks[i][0]}); // priority taskId userId
                int userId = tasks[i][0], taskId = tasks[i][1], priority = tasks[i][2];
                q.push({priority, taskId, userId});
                taskMap[taskId] = {priority, userId};
            }
    }
    
    void add(int userId, int taskId, int priority) {
        q.push({priority,taskId,userId});
        taskMap[taskId] = {priority, userId};
    }
    
    void edit(int taskId, int newPriority) {
        // vector<vector<int>> vt;
        vector<int> vt=taskMap[taskId];
        int userId = vt[1];
        taskMap[taskId] = {newPriority, userId};
        q.push({newPriority, taskId, userId});
    }
    
    void rmv(int taskId) {
        taskMap.erase(taskId);
    }
    
    int execTop() {
        while (!q.empty()) {
            vector<int> top = q.top();
            int priority = top[0], taskId = top[1], userId = top[2];
            if (taskMap.find(taskId) != taskMap.end() && 
                taskMap[taskId][0] == priority) {
                q.pop();
                taskMap.erase(taskId);
                return userId;
            }
            q.pop(); // Remove invalid tasks
        }
        return -1;
    }
};

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


```
['Hash Table', 'Ordered Map', 'Sorting', 'Heap (Priority Queue)', 'C++', 'Java']