🚀 Max Profit in O(N log N)! 💰 Greedy & Binary Search 🌟
Intuition \uD83E\uDDE0\nWhen I first encountered this problem, I thought about matching each worker with the highest-paying job they can handle. The key idea is
# Intuition \uD83E\uDDE0\nWhen I first encountered this problem, I thought about matching each worker with the highest-paying job they can handle. The key idea is to ensure that each worker is assigned the most profitable job that does not exceed their capability. By sorting the jobs by difficulty and updating the profit values to reflect the maximum achievable profit up to that difficulty, we can efficiently determine the best job for each worker.\n\n# Approach \uD83D\uDE80\n1. **Combine and Sort**: \n   - Combine the difficulty and profit of each job into a vector of pairs.\n   - Sort this vector by the difficulty of the jobs.\n\n2. **Update Profits**: \n   - Iterate through the sorted vector and update the profit for each job to be the maximum profit achievable up to that job\'s difficulty. This way, for any given difficulty, we know the best possible profit.\n\n3. **Assign Jobs to Workers**: \n   - For each worker, use binary search (`upper_bound`) to find the most challenging job they can complete and add the corresponding profit to the total profit.\n\n# Complexity \uD83D\uDCC8\n- **Time Complexity**: \n  - Sorting the jobs takes (O(N log N)), where (N) is the number of jobs.\n  - Assigning jobs to workers involves a binary search for each worker, taking (O(M log N)), where (M) is the number of workers.\n  - Overall, the time complexity is (O(N log N + M log N)).\n\n- **Space Complexity**: \n  - We use a vector to store the difficulty and profit pairs, which takes (O(N)) space.\n  - Therefore, the space complexity is (O(N)).\n\n# Code \uD83D\uDCBB\n```cpp\n#include <vector>\n#include <algorithm>\n#include <climits>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        // Combine difficulty and profit into a vector of pairs\n        vector<pair<int, int>> diffProf;\n        for (int i = 0; i < profit.size(); i++) {\n            diffProf.push_back({difficulty[i], profit[i]});\n        }\n        \n        // Sort the pairs by difficulty\n        sort(diffProf.begin(), diffProf.end());\n\n        // Update the profits to the maximum profit achievable up to that difficulty\n        int maxCanDo = INT_MIN;\n        for (int i = 0; i < diffProf.size(); i++) {\n            maxCanDo = max(diffProf[i].second, maxCanDo);\n            diffProf[i].second = maxCanDo;\n        }\n\n        int ans = 0;\n\n        // For each worker, find the best job they can do\n        for (int capacity : worker) {\n            auto it = upper_bound(diffProf.begin(), diffProf.end(), make_pair(capacity + 1, 0));\n            if (it != diffProf.begin()) {\n                ans += prev(it)->second;\n            }\n        }\n\n        return ans;\n    }\n};\n```\n\nThis approach ensures that we efficiently maximize the total profit by leveraging sorting and binary search, making it both optimal and elegant! \uD83C\uDF1F
['C++']