100% Beats || C++ || Determine best possible profit for a given difficulty
Intuition\nAs we can clearly see, just because difficulty of a job is higher, that $\textbf{doesnot}$ mean that it will reward a better profit\n\n# Approach\nWe
# Intuition\nAs we can clearly see, just because difficulty of a job is higher, that $\\textbf{doesnot}$ mean that it will reward a better profit\n\n# Approach\nWe determine what is the best profit obtainable for a given difficulty by considering all the previous difficulties and their reward. To do this, we first create an array of $\\textit{pair <int, int>}$ for difficulty and profit, and sort it by difficulty. Next we iterate in this array keeping the maximum value we have seen so far for the difficulties. Lastly, we iterate through the workers and determine best value they can obtain using $\\textit{lower\\_bound}$ and add it to the net profit.\n\n# Complexity\n- Time complexity:\n$$O(n\\log{n} + m\\log{n})$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution\n{\npublic:\n    int maxProfitAssignment(vector<int> &difficulty, vector<int> &profit, vector<int> &worker)\n    {\n        int n = difficulty.size();\n        int net_profit = 0;\n        int max_profit = 0;\n        vector<pair<int, int>> arr;\n        for (int i = 0; i < n; i++)\n            arr.push_back({difficulty[i], profit[i]});\n        sort(arr.begin(), arr.end());\n        for (int i = 0; i < n; i++)\n        {\n            max_profit = max(max_profit, arr[i].second);\n            arr[i].second = max_profit;\n        }\n        for (int w : worker)\n        {\n            pair<int, int> val = {w + 1, 0};\n            vector<pair<int, int>>::iterator ptr = lower_bound(arr.begin(), arr.end(), val);\n            if (ptr == arr.begin() && (*ptr).first > w)\n                continue;\n            if (ptr == arr.end() || (*ptr).first > w)\n                ptr--;\n            net_profit += (*ptr).second;\n        }\n        return net_profit;\n    }\n};\n```\n\n# Please Upvote!!!\n\n![image.png](https://assets.leetcode.com/users/images/df44b72f-3410-4242-aafa-20d33e8fe1e7_1702280521.1919644.png)\n\n# Beats\n![image.png](https://assets.leetcode.com/users/images/3ad8ef6e-dd79-46d5-8ab2-e8f8eba95ed4_1718699035.8147979.png)\n
['Binary Search', 'C++']