Binary Search Approach C++ intuition explained
Intuition\n Describe your first thoughts on how to solve this problem. \nObviously, for ith worker we\'ll try to maximize the profit. So whatever tasks that can
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nObviously, for ith worker we\'ll try to maximize the profit. So whatever tasks that can be done by this worker we\'ll choose the max profit.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIf a worker can do tasks with difficulty i then he can do every task having difficulty <=i so if I somehow know the max profit among all such tasks that\'ll be the ans for that worker. This leads us to the binary search approach. Suppose I sort the tasks wrt to their difficulty and I know the max profit I can get from tasks having <=i diffculty that\'ll be the answer. Make a vector pair of {difficulty,profit}\ndo binary search on difficulty and take maximum of profit till that index which can be maintained by prefix maximum;\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n + mlog(n));\n- Space complexity:\n- O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& dif, vector<int>& profit, vector<int>& worker) {\n        \n        vector<pair<int,int>> a;\n        int n = dif.size();\n        for(int i = 0; i < n; i++) {\n            a.push_back( { dif[i], profit[i] } );\n        }\n        \n        sort(a.begin(), a.end());\n        vector<int> preMax(n);\n        \n        for(int i = 0; i < n; i++)\n        {\n            preMax[i] = (i-1>=0) ? max(preMax[i-1],a[i].second) : a[i].second;\n\n        }\n        \n        int ans = 0;\n        int m = worker.size();\n        for(int i = 0; i < m; i++)\n        {\n            pair<int,int> se = {worker[i],1e9};\n            int ind = upper_bound(a.begin(),a.end(),se) - a.begin();\n            if(ind==0) continue;\n            --ind;\n            \n            ans += preMax[ind];\n        }\n        return ans;\n    }\n};\n```
['Binary Search', 'Sorting', 'C++']