Greedy | 100% Faster
\n\n# Intuition\nSort jobs and workers, then iteratively assign the maximum profit each worker can achieve with available jobs, accumulating the total achievabl
![Screenshot 2024-06-18 142633.png](https://assets.leetcode.com/users/images/1e8346f6-6b1f-4a48-82ad-4e3fad5d93eb_1718701555.8516502.png)\n\n# Intuition\nSort jobs and workers, then iteratively assign the maximum profit each worker can achieve with available jobs, accumulating the total achievable profit.\n\n# Approach\n- Pair each job\'s difficulty with its profit.\n- Sort jobs by difficulty and workers by ability.\n- Iterate through workers, finding the maximum profit they can achieve with available jobs.\n- Accumulate the maximum profits to get the total achievable profit.\n- Sorting ensures efficient pairing of workers with jobs based on their abilities and job difficulties.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity: O(n)\n\n# Code\n```C++ []\n#define sort(a) sort(begin(a), end(a))\n#define opt() ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);\n\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        opt();\n        int res = 0, j = 0, best = 0;\n        vector<pair<int, int>> temp;\n        for(int i = 0; i < difficulty.size(); ++i) {\n            temp.push_back({difficulty[i], profit[i]});\n        }\n\n        sort(temp); sort(worker);\n        for(int work : worker) {\n            while(j < worker.size() && work >= temp[j].first) {\n                best = max(best, temp[j].second);\n                j++;\n            }\n            \n            res += best;\n        }\n\n        return res;\n    }\n};\n```\n```java []\nclass Solution {\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        int res = 0, j = 0, best = 0;\n        List<Pair<Integer, Integer>> temp = new ArrayList<>();\n        \n        for (int i = 0; i < difficulty.length; ++i) {\n            temp.add(new Pair<>(difficulty[i], profit[i]));\n        }\n        \n        temp.sort((a, b) -> a.getKey() - b.getKey());\n        Arrays.sort(worker);\n        \n        for (int work : worker) {\n            while (j < worker.length && work >= temp.get(j).getKey()) {\n                best = Math.max(best, temp.get(j++).getValue());\n            }\n            \n            res += best;\n        }\n        \n        return res;\n    }\n}\n```\n```python []\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        res, j, best, temp = 0, 0, 0, []\n        \n        for i in range(len(difficulty)):\n            temp.append((difficulty[i], profit[i]))\n        \n        temp.sort()\n        worker.sort()\n        \n        for work in worker:\n            while j < len(worker) and work >= temp[j][0]:\n                best = max(best, temp[j][1])\n                j += 1\n            \n            res += best\n        \n        return res\n```\n```javascript []\n/**\n * @param {number[]} difficulty\n * @param {number[]} profit\n * @param {number[]} worker\n * @return {number}\n */\nvar maxProfitAssignment = function(difficulty, profit, worker) {\n    let res = 0, j = 0, best = 0, temp = [];\n    \n    for (let i = 0; i < difficulty.length; ++i) {\n        temp.push([difficulty[i], profit[i]]);\n    }\n    \n    temp.sort((a, b) => a[0] - b[0]);\n    worker.sort((a, b) => a - b);\n    \n    for (let work of worker) {\n        while (j < worker.length && work >= temp[j][0]) {\n            best = Math.max(best, temp[j][1]);\n            j++;\n        }\n        \n        res += best;\n    }\n    \n    return res;\n};\n```\n```Go []\nfunc maxProfitAssignment(difficulty []int, profit []int, worker []int) int {\n    res, j, best := 0, 0, 0\n    temp := make([]pair, len(difficulty))\n\n    for i := range difficulty {\n        temp[i] = pair{difficulty[i], profit[i]}\n    }\n\n    sort.Slice(temp, func(i, j int) bool {\n        return temp[i].difficulty < temp[j].difficulty\n    })\n    sort.Ints(worker)\n\n    for _, work := range worker {\n        for j < len(worker) && work >= temp[j].difficulty {\n            best = max(best, temp[j].profit)\n            j++\n        }\n        res += best\n    }\n\n    return res\n}\n\ntype pair struct {\n    difficulty, profit int\n}\n```\n\n\n\n---\n\n**Arg arg arg arg! You couldn\'t maximize profit if a dollar walked up and bit you on the nose! Why don\'t you just stick to counting the pennies in the leave-a-penny tray?**\n\n![Mr Krabs.jpg](https://assets.leetcode.com/users/images/008595b5-1f72-42da-b333-d10efd7290d6_1718708108.396877.jpeg)\n\n\n
['Array', 'Greedy', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript']