Easy Greedy Solution | Explained✅🏆
Intuition\nTo maximize the total profit, we need to assign each worker to the most profitable job they can perform based on their ability. Sorting both jobs and
# Intuition\nTo maximize the total profit, we need to assign each worker to the most profitable job they can perform based on their ability. Sorting both jobs and workers allows us to efficiently match each worker to the best possible job they can do.\n\n# Approach\n1. **Pairing Difficulty and Profit**: Create a vector of pairs where each pair consists of a job\'s difficulty and its corresponding profit.\n2. **Sorting**:\n   - Sort the job pairs based on difficulty.\n   - Sort the worker abilities.\n3. **Maximizing Profit**:\n   - Iterate through the sorted list of workers.\n   - For each worker, update the maximum profit they can achieve based on their ability by iterating through the sorted jobs.\n   - Accumulate this profit for each worker to get the total profit.\n\n# Complexity\n- **Time complexity**: \n  - Sorting the jobs and workers takes \\(O(n \\log n + m \\log m)\\), where \\(n\\) is the number of jobs and \\(m\\) is the number of workers.\n  - Iterating through the jobs and workers takes \\(O(n + m)\\).\n  - Overall, the time complexity is \\(O(n \\log n + m \\log m)\\).\n\n- **Space complexity**: \n  - We use extra space for storing the job pairs, which takes \\(O(n)\\).\n  - Overall, the space complexity is \\(O(n)\\).\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        vector<pair<int, int>> pd;\n        for (int i = 0; i < difficulty.size(); i++) {\n            pd.push_back({difficulty[i], profit[i]});\n        }\n\n        // Sort jobs by difficulty\n        sort(pd.begin(), pd.end());\n        // Sort workers by their ability\n        sort(worker.begin(), worker.end());\n\n        int maxProfit = 0, i = 0;\n        long long totalProfit = 0;\n\n        for (int w : worker) {\n            // Update maxProfit with the best profit for jobs the current worker can do\n            while (i < pd.size() && pd[i].first <= w) {\n                maxProfit = max(maxProfit, pd[i].second);\n                i++;\n            }\n            totalProfit += maxProfit;\n        }\n\n        return totalProfit;\n    }\n};\n
['Array', 'Two Pointers', 'Binary Search', 'Greedy', 'Sorting', 'C++']