Greedy Picking With Binary Search | Java | C++
Intuition, approach, and complexity discussed in video solution in details\nhttps://youtu.be/Ptyvx7cHFtY\n# Code\nJava\n\nclass Solution {\n    public int maxPr
# Intuition, approach, and complexity discussed in video solution in details\nhttps://youtu.be/Ptyvx7cHFtY\n# Code\nJava\n```\nclass Solution {\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        int diffLen = difficulty.length, wLen = worker.length;\n        int diffProf[][] = new int[diffLen][2];\n        for(int indx = 0; indx < diffLen; indx++){\n            diffProf[indx][0] = difficulty[indx];\n            diffProf[indx][1] = profit[indx]; \n        }\n        Arrays.sort(diffProf, (a, b)->(a[0] - b[0]));\n        int maxProfTill[] = new int[diffLen];\n        for(int indx = 0; indx < diffLen; indx++){\n            maxProfTill[indx] = Math.max(((indx > 0) ? (maxProfTill[indx-1]) : 0), diffProf[indx][1]);\n        }\n        int totalProf = 0;\n        for(int wIndx = 0; wIndx < wLen; wIndx++){\n            int maxDiffIndx = findMaxDiffJob(diffProf, worker[wIndx]);\n            if(maxDiffIndx != -1){\n                 totalProf += maxProfTill[maxDiffIndx];                \n            }\n        }\n        return totalProf;\n    }\n    private int findMaxDiffJob(int diffProf[][], int workerCap){\n        int left = 0, right = diffProf.length-1;\n        int ansIndx = -1;\n        while(left <= right){\n            int midIndx = left + (right - left) / 2;\n            if(workerCap >= diffProf[midIndx][0]){\n                ansIndx = midIndx;\n                left = midIndx + 1;\n            }else{\n                right = midIndx - 1;\n            }\n        }\n        return ansIndx;\n    }\n}\n```\nC++\n```\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        int diffLen = difficulty.size(), wLen = worker.size();\n        vector<pair<int, int>> diffProf(diffLen);\n        \n        for(int indx = 0; indx < diffLen; indx++){\n            diffProf[indx] = {difficulty[indx], profit[indx]};\n        }\n        \n        sort(diffProf.begin(), diffProf.end(), [](const pair<int, int>& a, const pair<int, int>& b) {\n            return a.first < b.first;\n        });\n        \n        vector<int> maxProfTill(diffLen);\n        for(int indx = 0; indx < diffLen; indx++){\n            maxProfTill[indx] = max((indx > 0 ? maxProfTill[indx - 1] : 0), diffProf[indx].second);\n        }\n        \n        int totalProf = 0;\n        for(int wIndx = 0; wIndx < wLen; wIndx++){\n            int maxDiffIndx = findMaxDiffJob(diffProf, worker[wIndx]);\n            if(maxDiffIndx != -1){\n                 totalProf += maxProfTill[maxDiffIndx];                \n            }\n        }\n        \n        return totalProf;\n    }\n    \nprivate:\n    int findMaxDiffJob(const vector<pair<int, int>>& diffProf, int workerCap){\n        int left = 0, right = diffProf.size() - 1;\n        int ansIndx = -1;\n        while(left <= right){\n            int midIndx = left + (right - left) / 2;\n            if(workerCap >= diffProf[midIndx].first){\n                ansIndx = midIndx;\n                left = midIndx + 1;\n            } else {\n                right = midIndx - 1;\n            }\n        }\n        return ansIndx;\n    }\n};\n\n```
['Array', 'Binary Search', 'Greedy', 'Sorting', 'C++', 'Java']