Max Heap and 2 Hash Maps Solution | Rust | Python
IntuitionThe first thing that come up in this problem is try priority queue (max heap), but we have a challange: how to implement priority edit (since we can't
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The first thing that come up in this problem is try priority queue (max heap), but we have a challange: how to implement priority edit (since we can't easily retrieve arbitrary element in the queue). How do we tame this challange? 

# Approach
<!-- Describe your approach to solving the problem. -->
Lets define 2 hash maps `prs` and `usrs`. The first one will map tasks to priorities and the second one will map tasks to users. Now when we edit priority we push task with new priority to priority queue and then we have more than 1 priority for the same task, but we also edit map of tasks to priorities `prs`. By this, we ensure that knowledge of the most recent priority assigned to all tasks (and users). When we remove some task from task manager, we should remove corresponding entries in maps to users and to priorities. 

So, when we run `exec_top` method we try to get task with the highest priority and execute the task if its priority equals to the most recent priority (i. e. value of `prs[task_id]`) for this task and this task is still tracked by task manager

# Complexity
- Time complexity: $$O(n \log(n))$$
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(n)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```rust []
use std::collections::{BinaryHeap, HashMap};

struct TaskManager {
    tasks: BinaryHeap<(i32, i32, i32)>,
    prs: HashMap<i32, i32>,
    usrs: HashMap<i32, i32>
}


/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl TaskManager {

    fn new(tasks: Vec<Vec<i32>>) -> Self {
        let mut tasks_: BinaryHeap<(i32, i32, i32)> = BinaryHeap::new();
        let mut prs_: HashMap<i32, i32> = HashMap::new();
        let mut usrs_: HashMap<i32, i32> = HashMap::new();

        for triple in tasks.iter() {
            let (user_id, task_id, priority) = (triple[0], triple[1], triple[2]);
            prs_.insert(task_id, priority);
            usrs_.insert(task_id, user_id);
            tasks_.push((priority, task_id, user_id))
        }
        
        Self {
            tasks: tasks_,
            prs: prs_,
            usrs: usrs_
        }
    }
    
    fn add(&mut self, user_id: i32, task_id: i32, priority: i32) {
        self.prs.insert(task_id, priority);
        self.usrs.insert(task_id, user_id);
        self.tasks.push((priority, task_id, user_id))
    }
    
    fn edit(&mut self, task_id: i32, new_priority: i32) {
        self.prs.insert(task_id, new_priority);
        self.tasks.push((new_priority, task_id, self.usrs[&task_id]))
    }
    
    fn rmv(&mut self, task_id: i32) {
        self.prs.insert(task_id, -1);
        self.usrs.insert(task_id, -1);
    }
    
    fn exec_top(&mut self) -> i32 {
        let (mut pr, mut tid, mut uid) = match self.tasks.pop() {
            Some(x) => x,
            None => { return -1 }
        };
        while pr != self.prs[&tid] || uid != self.usrs[&tid] {
            (pr, tid, uid) = match self.tasks.pop() {
                Some(x) => x,
                None => { return -1 }
            };
        }
        self.rmv(tid);
        uid
    }
}

/**
 * Your TaskManager object will be instantiated and called as such:
 * let obj = TaskManager::new(tasks);
 * obj.add(userId, taskId, priority);
 * obj.edit(taskId, newPriority);
 * obj.rmv(taskId);
 * let ret_4: i32 = obj.exec_top();
 */
```
```python []
class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.tasks = [(-priority, -taskId, userId) for userId, taskId, priority in tasks]
        heapify(self.tasks)
        self.prs = {tid:pr for _, tid, pr in tasks}
        self.usrs = {tid:uid for uid, tid, _ in tasks}
    

    def add(self, userId: int, taskId: int, priority: int) -> None:
        heappush(self.tasks, (-priority, -taskId, userId))
        self.prs[taskId] = priority
        self.usrs[taskId] = userId
        

    def edit(self, taskId: int, newPriority: int) -> None:
        if newPriority != self.prs[taskId]:
            self.prs[taskId] = newPriority
            heappush(self.tasks, (-newPriority, -taskId, self.usrs[taskId]))       
        

    def rmv(self, taskId: int) -> None:
        self.prs[taskId] = -1
        self.usrs[taskId] = -1
        

    def execTop(self) -> int:
        if not self.tasks:
            return -1
        pr, tid, uid = heappop(self.tasks)
        pr, tid = -pr, -tid
        while pr != self.prs[tid] or uid != self.usrs[tid]:
            if not self.tasks:
                return -1
            pr, tid, uid = heappop(self.tasks)
            pr, tid = -pr, -tid

        self.rmv(tid)
        return uid


# 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()
```
['Hash Table', 'Heap (Priority Queue)', 'Python', 'Python3', 'Rust']