Easy to understand C++ Solution beats 90% | Binary Search + Sort | Linear Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nEach worker can only do the work that is equal or lower to his ability, so we need to h
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nEach worker can only do the work that is equal or lower to his ability, so we need to have order based on the difficulty of the tasks and we also sort the workers based on their ability.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe create a vector of pairs of difficulty and profit and sort it. We also sort the worker array. Now we carry out binary search to get the max work that can be done by the worker, now we carry out a linear scan from cov variable to the searched index to get the max profit for the work possible. We continue in a similar fashion for each of the workers and finally we get the desired result.\n# Complexity\n- Time complexity:O(nlogn)\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        vector<pair<int,int>> vec(difficulty.size());\n        for(int i=0; i<difficulty.size(); i++){\n            vec[i] = {difficulty[i], profit[i]};\n        }\n        auto comp = [&](pair<int,int> a, pair<int,int> b){\n            if(a.first < b.first)return true;\n            return false;\n        };\n        sort(vec.begin(), vec.end(), comp);\n        sort(worker.begin(), worker.end());\n        int res = 0;\n        int cov = 0;\n        int maxProf = 0;\n        for(int i=0; i<worker.size(); i++){\n            int getMid = binarySearch(vec, worker[i]);\n            for(int i=cov; i<=getMid; i++){\n                maxProf = max(maxProf, vec[i].second);\n            }\n            cov = max(0,getMid);\n            res += maxProf;\n        }\n        return res;\n    }\n    int binarySearch(vector<pair<int,int>>& vec,int target){\n        int l = 0;\n        int r = vec.size()-1;\n        int res = -1;\n        while(l<=r){\n            int mid = (l+r)/2;\n            if(vec[mid].first <= target){\n                res = mid;\n                l = mid + 1;\n            }else{\n                r = mid - 1;\n            } \n        }\n        return res;\n    }\n};\n```\n\n# Linear Solution Depends on the maximum difficulty\nWe create an array of size max difficulty + 1 and then for each difficulty[i], we fill in the values into the array and then we iterate through the array an create prefix maximum value array by looking at the previous value and deciding if current value is greatest seen till now or not. If current value is not greatest, we replace it with greatest seen till now. Then for each worker\'s ability, we check based on the array, we keep a check by taking the min(worker[i],max_difficulty), so that the values don\'t go out of bound.\n\n# Time Complexity : O(max_element) + O(n+m)\n\n# Space Complexity : O(max_element)\n\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        int ma = *max_element(difficulty.begin(),difficulty.end());\n        int arr[ma+1];\n        for(int i=0; i<ma+1; i++){\n            arr[i] = 0;\n        }\n        for(int i = 0; i<difficulty.size(); i++){\n            arr[difficulty[i]] = max(arr[difficulty[i]],profit[i]);\n        }\n        for(int i=1; i<ma+1; i++){\n            arr[i] = max(arr[i-1],arr[i]);\n        }\n        int res = 0;\n        for(int i=0; i<worker.size(); i++){\n            res += arr[min(worker[i],ma)];\n        }\n        return res;\n    }\n};\n```
['Binary Search', 'Sorting', 'C++']