Simple Heap Solution using Max Heap and Min Heap!! Detailed Explanation!!
Intuition\n Describe your first thoughts on how to solve this problem. \nOne worker can do at most one job. So we choose the the highest profit with the difficu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nOne worker can do at most one job. So we choose the the highest profit with the difficulty level the worker can handle. If no such job is present then that worker is idle. However one job can be done by multiple workers.\nTherefore we need to pair up profit with its difficulty and sort them is descending order. But why use sort and go through the whole array when we can use heaps.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSort the worker array in ascending order so the difficulty they can handle is in increasing fashion.\nIn the max heap, store it in form of {profit, difficulty} so it gets stored in descending order according to profits.\nIn the min heap, store it in form of {difficulty, profit} so it gets stored in ascending order according to difficulty.\nNow we only need to push a job into max heap if the current worker can handle it, otherwise it stays in the min heap.\nOur most profitable job will always be at the top of max heap.\n\n# Complexity\n- Time complexity: O(N*log(N))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        priority_queue<pair<int,int>> pq; //We will store profit, difficulty\n                                         // of ith job in max heap.\n        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> storage;\n        //min heap to store the jobs whose difficulty level exceed the first job workers capability\n        int totalProfit = 0, n=difficulty.size(), m=worker.size();\n        sort(worker.begin(), worker.end());\n        for(int i=0; i<n; i++)\n        {\n            if(difficulty[i] <= worker[0])\n                pq.push({profit[i], difficulty[i]});\n            else\n                storage.push({difficulty[i], profit[i]});\n        }\n        for(int i=0; i<worker.size();)\n        {\n            if(!pq.empty())\n                totalProfit += pq.top().first;\n            i++; // to move to next worker, not given in for condition \n                // as otherwise we need to make checks below. \n            if(i == worker.size())\n                break;\n            while(!storage.empty())\n            {\n                if(storage.top().first <= worker[i])\n                {\n                    pq.push({storage.top().second,storage.top().first});\n                    storage.pop();\n                }\n                else\n                    break;\n            }\n        }\n        return totalProfit;\n    }\n};\n```
['Array', 'Greedy', 'Sorting', 'Heap (Priority Queue)', 'C++']