All Kind Of Solution With Explanation
All These Solutions except the very last one are inspired by @lee215 and @votrubac\n## Solution 1\n\n1.Create a vector where each element is a pair comprised di
### All These Solutions except the very last one are inspired by @lee215 and @votrubac\n## Solution 1\n```\n1.Create a vector where each element is a pair comprised difficulty[i] and profit[i] for each i.\n2.Sort it and it will be sorted by difficulty[i] by default.\n3.Also sort the \'worker\', now for each worker[i] traverse \'jobs\' till jobs[j].first <= worker[i].\n   We don\'t need to traverse \'j always from the beginning as \n   "one job can be completed multiple times" means \n   \n   10 20 10 5   - profit     \n   4  5  7  9   - difficulty \n   2  4  8  10  - worker\n\n   for worker[2] = 8, I can do difficulty : 4,5,7 but 5 pay me highest(20) so I\'ll take 5\n   because I can do any job which difficulty level <= my difficulty level.\n   So using max() we can easily find high paid level as we have "sorted jobs". \n   \n   Of course in pair difficult[i] is the first one cause we need to compare worker[i] with \n   difficulty[i] and both denotes \'difficulty level\'.\n```\n\n```CPP []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        vector<pair<int,int>> jobs;\n        for(int i=0; i<difficulty.size(); i++)\n            jobs.push_back({difficulty[i],profit[i]});\n\n        sort(begin(jobs),end(jobs));\n        sort(begin(worker),end(worker));\n\n        int j = 0, best = 0, sum = 0;\n        for(int & it : worker)\n        {\n            while(j<jobs.size() && jobs[j].first<=it)\n                best = max(best, jobs[j].second), j++;\n            sum += best;\n        }\n        return sum;\n    }\n};\n```\n```Python []\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        jobs = sorted(zip(difficulty, profit))\n        j = best = ans = 0\n        for ability in sorted(worker):\n            while j < len(jobs) and jobs[j][0] <= ability:\n                best = max(best, jobs[j][1])\n                j += 1\n            ans += best\n        \n        return ans\n```\n```\nTime complexity  : O(nlogn)\nSpace complexity : O(n)\n```\n## Solution 2 :\n```\nmax(m[difficulty[i]], profit[i]) had done because there can be duplicate in \'difficulty\'.\n\nDifficulty      Profit                                     Profit\n----------     --------         ___________               --------\n    4             20           |            |                20\n    6             10    ---->  |    Second  |  ----->        20\n    8             30           |    For     |                30\n    10            20           |    Loop    |                30\n\nreturn accumulate(begin(worker), end(worker), 0, [m](int sum, int value)...\n                                              |\n              sum = -------------------------\n              and value = each value in worker\n          \n              1 2 4 5 8 9\n              upper_bound(5) = 8 \n              lower_bound(5) = 5 but\n              1 2 4 8 9\n              lower_bound(5) = 8. Upper_bound = 1 variation where lower_bound = 2 variation.\nThat\'s why upper_bound chosen. prev(upper_bound(iterator)) is the iterator we need here always.\n```\n```CPP []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) \n    {\n        map<int, int> m;\n        for(int i=0; i<difficulty.size(); i++)\n            m[difficulty[i]] = max(m[difficulty[i]], profit[i]);\n        \n        for(auto it = next(m.begin()); it!= m.end(); it++)\n            it->second = max(prev(it)->second, it->second);\n        \n        return accumulate(begin(worker), end(worker), 0, [m](int sum, int value){ return sum + prev(m.upper_bound(value))->second; });\n    }\n};\n```\n```\nTime  Complexity : O(nlogn) as we took map.\nSpace Complexity : O(n)\n```\n## Solution 3 :\n```\nHere difficulty[i] = index and profit[i] = value of the " counting sort \'jobs\' "\n\ndifficulty = [2,4,6,8,10], profit = [20,10,15,40,30], worker = [4,5,6,7]\n\n0  0  20  0   10  0   15  0   40  0   50 ............. (profit)\n0  1  2   3   4   5   6   7   8   9   10 ............. (difficulty)\n                  \n                    * After the second for loop *\n                     \n0  0  20  20  20  20  20  20  40  40  40 ............. (profit)\n0  1  2   3   4   5   6   7   8   9   10 ............. (difficulty)\n\nIn the map solution when we "accumulate"d for each worker[i] say for 5 we had to go for \nprev(upper_bound) = prev(5) =  4 here, but here in counting sort we have 5 to access directly, \n\n                          \'   20 (profit)\n                            5  (difficulty)   \'\n\nwe don\'t need any upper bound or traversing the array to get the value. So this solution is fast.\n```\n```CPP []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) \n    {\n        int jobs[100001] = {0};\n        for(int i=0; i<difficulty.size(); i++)\n                jobs[difficulty[i]] = max(jobs[difficulty[i]], profit[i]);\n\n        for(int i=1; i<100001; i++)\n            jobs[i] = max(jobs[i], jobs[i-1]);\n\n        return accumulate(begin(worker), end(worker), 0, [jobs](int s, int v){ return s + jobs[v]; });\n    }\n};\n```\n```\nYou can also optimize it by below. We only need the maximum element of \'worker\'.\n                2 4 6 8 9 10 (difficulty)\n                2 3 5 7      (worker)\nas we need till \'7\', so we don\'t care values > 7 in \'difficulty\'. \nMake sure the value in \'difficulty\' is <= the maximum in \'worker\'.\n```\n```CPP []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) \n    {\n        int m = *max_element(begin(worker), end(worker)) + 1;\n        vector<int> jobs(m, 0);\n        for(int i=0; i<difficulty.size(); i++)\n            if(difficulty[i] < m)\n                jobs[difficulty[i]] = max(jobs[difficulty[i]], profit[i]);\n\n        for(int i=1; i<m ;i++)\n            jobs[i] = max(jobs[i], jobs[i-1]);\n\n        return accumulate(begin(worker), end(worker), 0, [jobs](int s, int v){ return s + jobs[v]; });\n    }\n};\n```\n```\nTime  Complexity : O(n + m)\nSpace Complexity : O(m)\n```\n## If the post was helpful an upvote will really make me happy:)
['C++', 'Python3']