Brute Force-Ordered Set | Optimal Ordered Set + HashMap
Intuition
Just a normal ordered set is enough to code for brute force .
In rmv function we are using find_if function which takes o(n) in worst case.
So to opti
# Intuition
- Just a normal ordered set is enough to code for brute force .
- In rmv function we are using find_if function which takes o(n) in worst case.
- So to optimise this we can use map to store info about userId and priority instead of using find_if function to find these things.
Intuition definitely comes from lru cache and lfu cache if you know the core of those problems.


# Approach
- Insert values in map and set on add call.
- In set priority should be before taskid and userId.
- Map stores taskid's userid and priority.
- When edit is called we simple access userId and prior using taskid given.
- Now we erase from set & map using these values.
- Insert new values in set and map.
- For rmv function do same but just erase.
- Exectop function access last element from set as it is largest and return its userid. Also call remove(taskID) to remove that value as well.

# Complexity
- Time complexity:
Brute force:- O(N)
Optimal:- O(log N)

- Space complexity:
- Brute:O(N)
Optimal:O(N+N)

# Code
```cpp []
// struct CompareBySecond {
//     bool operator()(const std::pair<int, std::pair<int, int>>& a,
//                     const std::pair<int, std::pair<int, int>>& b) const {
//         return a.second.first < b.second.first || 
//               (a.second.first == b.second.first);
//     }
// };

// class TaskManager {
// public:
//     set<pair<int,pair<int,int>>>st;
//     TaskManager(vector<vector<int>>& tasks) {
//         for(auto task:tasks){
//             st.insert({task[2],{task[1],task[0]}});
//         }
//     }
    
//     void add(int userId, int taskId, int priority) {
//         st.insert({priority,{taskId,userId}});
//     }
    
//     void edit(int taskId, int newPriority) {
//         //this find_if can be optimised using a map for storage of userid and prior for given taskId
//         auto it = std::find_if(st.begin(), st.end(), [taskId](const auto& p) {
//             return p.second.first == taskId;
//         });
//         int userId=it->second.second;
        
//         st.erase(it);
//         st.insert({newPriority,{taskId,userId}});
//     }
    
//     void rmv(int taskId) {
//         auto it = std::find_if(st.begin(), st.end(), [taskId](const auto& p) {
//             return p.second.first == taskId;
//         });
//         st.erase(it);
//     }
    
//     int execTop() {
//         // for(auto it:st){
//         //     cout<<it.first<<" "<<it.second.first<<" "<<it.second.second<<endl;
//         // }
//         if(st.size()<1)return -1;
//         if(st.size()<2){
//             auto removeIter = --st.end();
//             int finalVal = removeIter->second.second;

//         // Remove the element from the set
//             st.erase(removeIter);
            
//             return finalVal;
//         }

//         auto topVal = prev(st.end());        // Last element
//         auto secondTopVal = prev(topVal);    // Second last element
//         // cout<<topVal->first<<" "<<secondTopVal->first<<endl;
//         // Iterator to the element to remove
//         auto removeIter = st.end();

//         // Compare first elements of the pairs
//         if (topVal->first == secondTopVal->first) {
//             // Compare second.first elements
//             if (topVal->second.first >= secondTopVal->second.first) {
//                 removeIter = topVal;
//             } else {
//                 removeIter = secondTopVal;
//             }
//         }
//         else {
//             removeIter = topVal; // Default to removing the top value
//         }

//         // Get the second.second value of the element to be removed
//         int finalVal = removeIter->second.second;

//         // Remove the element from the set
//         st.erase(removeIter);

//         return finalVal;
//     }
// };
//O(N) solution

class TaskManager {
public:
    set<pair<long long,int>>st;
    map<int,pair<long long,int>>mp;
    TaskManager(vector<vector<int>>& tasks) {
        for(auto task:tasks){
            int userId=task[0];
            int taskId=task[1];
            int prior=task[2];
            mp[taskId]={prior,userId};
            st.insert({prior,taskId});
        }
    }
    
    void add(int userId, int taskId, int priority) {
        mp[taskId]={priority,userId};
        st.insert({priority,taskId});
    }
    
    void edit(int taskId, int newPriority) {
        auto p=mp[taskId];
        int userId=p.second;
        int oldPrior=p.first;
        st.erase({oldPrior,taskId});
        mp.erase(taskId);
        st.insert({newPriority,taskId});
        mp[taskId]={newPriority,userId};
    }
    
    void rmv(int taskId) {
        auto p=mp[taskId];
        int userId=p.second;
        int oldPrior=p.first;
        st.erase({oldPrior,taskId});
        mp.erase(taskId);
    }
    
    int execTop() {
        if(st.empty())return -1;
        //just give the top last element
        auto lastEl=--st.end();
        int lastPrior=lastEl->first;
        int taskId=lastEl->second;
        int userId=mp[taskId].second;
        rmv(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();
 */
```
['Ordered Map', 'Ordered Set', 'C++']