Beats 100% || Priority_Queue & HashMap Solution || C++
IntuitionThe goal is to design a task management system that allows efficient addition, modification, removal, and execution of tasks based on their priority. A
# Intuition
The goal is to design a task management system that allows efficient addition, modification, removal, and execution of tasks based on their priority. A priority queue is a natural choice for this problem, as it provides quick access to the task with the highest priority. To handle dynamic updates and removals, we use additional data structures for fast lookups.

# Approach
The solution uses the following data structures:

1. Priority Queue (pq): Stores tasks along with their priority for efficient retrieval of the highest-priority task.
HashMaps (p_task and usr_task):
2. p_task: Maps task IDs to their current priorities.
usr_task: Maps task IDs to their associated user IDs.

**Key Operations:**
1. Initialization (TaskManager):
    - During initialization, we iterate over the list of tasks, updating the p_task and usr_task maps and pushing tasks into the priority queue.

2. Add Task (add):
    - Update p_task and usr_task with the new task details.
    - Push the task into the priority queue.
    - Edit Task Priority (edit):

3. Update the priority of a task in p_task.
    - Push the updated task into the priority queue. Duplicate entries in the queue are resolved during execution.
4. Remove Task (rmv):

    - Mark the task as removed by setting its priority to -1 in p_task.
    - The task remains in the priority queue but will be ignored during execution.
5. Execute Top Priority Task (execTop):

    - Repeatedly pop tasks from the priority queue until we find one that:
        - Exists (p_task priority is not -1).
        - Has the same priority as the one stored in p_task.
    - Mark the task as executed (p_task set to -1) and return the user ID associated with the task.
    - Return -1 if the queue is empty or no valid tasks remain.

# Complexity
- Time complexity:
    - Initialization (TaskManager): O(nlogn), where n is the number of tasks, as each insertion into the priority queue takes O(long).
    - Add/Edit: O(logn), due to insertion into the priority queue
    - Remove: O(1), as it directly updates the hash map.
    - Execute Top: O(logn) on average, as it pops elements from the queue. In the worst case, it might need to process all n tasks, making it O(nlogn).



- Space complexity:
    - Priority Queue: O(n), where n is the number of tasks stored.
    - Hash Maps: O(2n), storing task priorities and user mappings.
    - Overall: O(n).

# Code
```cpp []
class TaskManager {
private:
    priority_queue<pair<int,int>> pq;
    unordered_map<int,int> p_task;
    unordered_map<int,int> usr_task;
    
public:
    TaskManager(vector<vector<int>>& tasks) {
        int n=tasks.size();
        for(int i=0;i<n;i++){
            int usr=tasks[i][0];
            int task=tasks[i][1];
            int prio=tasks[i][2];
            p_task[task]=prio;
            usr_task[task]=usr;
            pq.push({prio,task});

        }
    }
    
    void add(int userId, int taskId, int priority) {

        p_task[taskId]=priority;
        usr_task[taskId]=userId;        
        pq.push({priority,taskId});
    }
    
    void edit(int taskId, int newPriority) {
        p_task[taskId]=newPriority;
        pq.push({newPriority,taskId});
    }
    
    void rmv(int taskId) {
        p_task[taskId]=-1;
    }
    
    int execTop() {
        if(pq.empty())return -1;
        while(!pq.empty()){
            pair<int,int> p=pq.top();
            if(p_task[p.second]==-1){
                pq.pop();
            }
            else if(p_task[p.second]<p.first){
                pq.pop();                
            }
            else{
                pq.pop();
                p_task[p.second]=-1;
                return usr_task[p.second];
            }
        }
        return -1;
    }
};
['C++']