✅Beats 100% -Explained with [ Video ] -C++/Java/Python/JS -DP -Interview Solution
\n\n\n# YouTube Video Explanation:\n\n **If you want a video for this question please write in the comments** \n\nhttps://youtu.be/vL6ZbaP9API\n\n\n\uD83D\uDD25
![Screenshot 2024-06-18 063442.png](https://assets.leetcode.com/users/images/3e125df7-9de3-4af9-a26a-d02270de5fa6_1718673560.0957673.png)\n\n\n# YouTube Video Explanation:\n\n<!-- **If you want a video for this question please write in the comments** -->\n\nhttps://youtu.be/vL6ZbaP9API\n\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2100 Subscribers*\n*Current Subscribers: 2040*\n\n---\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires assigning the most profitable jobs to workers based on their ability to handle the job difficulty. Each worker can complete only one job, and each job can be completed multiple times by different workers. To maximize the total profit, we need to ensure that each worker is assigned the most profitable job they can complete given their skill level.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initialization**: \n   - Determine the maximum job difficulty.\n   - Initialize a `maxProfitUpToDifficulty` array to store the maximum profit for each difficulty level up to the maximum difficulty.\n\n2. **Fill the Profit Lookup Table**:\n   - For each job, update the `maxProfitUpToDifficulty` array to ensure it holds the maximum profit for the given difficulty.\n   - Convert the `maxProfitUpToDifficulty` array to a cumulative maximum profit array, where each index `i` will have the maximum profit possible for difficulties from `0` to `i`.\n\n3. **Calculate Total Profit**:\n   - For each worker, use their ability to look up the corresponding maximum profit from the `maxProfitUpToDifficulty` array and sum up the total profit.\n\n# Complexity\n- **Time Complexity**: \\( O(n + m + d) \\), where \\( n \\) is the number of jobs, \\( m \\) is the number of workers, and \\( d \\) is the maximum difficulty.\n- **Space Complexity**: \\( O(d) \\) for the `maxProfitUpToDifficulty` array.\n\n---\n\n# Step by Step Explanation\n\n\n#### Step 1: Identify Maximum Difficulty\n\nFirst, we find the maximum difficulty among all jobs to determine the size of our dynamic programming (DP) array.\n\n```java\nint maxDifficulty = 0;\nfor (int d : difficulty) {\n    maxDifficulty = Math.max(maxDifficulty, d);\n}\n```\n\n| Job | Difficulty |\n|-----|------------|\n| 1   | 2          |\n| 2   | 4          |\n| 3   | 6          |\n| 4   | 8          |\n| 5   | 10         |\n\n- `maxDifficulty = 10`\n\n---\n\n#### Step 2: Create Profit Lookup Table\n\nCreate an array `maxProfitUpToDifficulty` where each index represents the maximum profit obtainable for that difficulty.\n\n```java\nint[] maxProfitUpToDifficulty = new int[maxDifficulty + 1];\nfor (int i = 0; i < difficulty.length; i++) {\n    maxProfitUpToDifficulty[difficulty[i]] = Math.max(maxProfitUpToDifficulty[difficulty[i]], profit[i]);\n}\n```\n\n| Difficulty | Profit | maxProfitUpToDifficulty |\n|------------|--------|-------------------------|\n| 2          | 10     | 10                      |\n| 4          | 20     | 20                      |\n| 6          | 30     | 30                      |\n| 8          | 40     | 40                      |\n| 10         | 50     | 50                      |\n\n---\n\n#### Step 3: Convert to Cumulative Maximum Profit\n\nUpdate the `maxProfitUpToDifficulty` array to ensure each index `i` contains the maximum profit possible for difficulties from `0` to `i`.\n\n```java\nfor (int i = 1; i <= maxDifficulty; i++) {\n    maxProfitUpToDifficulty[i] = Math.max(maxProfitUpToDifficulty[i], maxProfitUpToDifficulty[i - 1]);\n}\n```\n\n| Difficulty | maxProfitUpToDifficulty (Cumulative) |\n|------------|--------------------------------------|\n| 0          | 0                                    |\n| 1          | 0                                    |\n| 2          | 10                                   |\n| 3          | 10                                   |\n| 4          | 20                                   |\n| 5          | 20                                   |\n| 6          | 30                                   |\n| 7          | 30                                   |\n| 8          | 40                                   |\n| 9          | 40                                   |\n| 10         | 50                                   |\n\n---\n\n#### Step 4: Calculate Total Profit\n\nFor each worker, determine the maximum profit they can earn using the `maxProfitUpToDifficulty` array.\n\n```java\nint totalProfit = 0;\nfor (int ability : worker) {\n    if (ability > maxDifficulty) {\n        totalProfit += maxProfitUpToDifficulty[maxDifficulty];\n    } else {\n        totalProfit += maxProfitUpToDifficulty[ability];\n    }\n}\n```\n\n| Worker Ability | Max Profit |\n|----------------|------------|\n| 4              | 20         |\n| 5              | 20         |\n| 6              | 30         |\n| 7              | 30         |\n\n- **Total Profit**: `20 + 20 + 30 + 30 = 100`\n\n---\n\n# Code\n```java []\nclass Solution {\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        int maxDifficulty = 0;\n        for (int d : difficulty) {\n            maxDifficulty = Math.max(maxDifficulty, d);\n        }\n\n        int[] maxProfitUpToDifficulty = new int[maxDifficulty + 1];\n        for (int i = 0; i < difficulty.length; i++) {\n            maxProfitUpToDifficulty[difficulty[i]] = Math.max(maxProfitUpToDifficulty[difficulty[i]], profit[i]);\n        }\n\n        for (int i = 1; i <= maxDifficulty; i++) {\n            maxProfitUpToDifficulty[i] = Math.max(maxProfitUpToDifficulty[i], maxProfitUpToDifficulty[i - 1]);\n        }\n\n        int totalProfit = 0;\n        for (int ability : worker) {\n            if (ability > maxDifficulty) {\n                totalProfit += maxProfitUpToDifficulty[maxDifficulty];\n            } else {\n                totalProfit += maxProfitUpToDifficulty[ability];\n            }\n        }\n\n        return totalProfit;\n    }\n\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        int maxDifficulty = *max_element(difficulty.begin(), difficulty.end());\n        vector<int> maxProfitUpToDifficulty(maxDifficulty + 1, 0);\n\n        for (int i = 0; i < difficulty.size(); ++i) {\n            maxProfitUpToDifficulty[difficulty[i]] = max(maxProfitUpToDifficulty[difficulty[i]], profit[i]);\n        }\n\n        for (int i = 1; i <= maxDifficulty; ++i) {\n            maxProfitUpToDifficulty[i] = max(maxProfitUpToDifficulty[i], maxProfitUpToDifficulty[i - 1]);\n        }\n\n        int totalProfit = 0;\n        for (int ability : worker) {\n            if (ability > maxDifficulty) {\n                totalProfit += maxProfitUpToDifficulty[maxDifficulty];\n            } else {\n                totalProfit += maxProfitUpToDifficulty[ability];\n            }\n        }\n\n        return totalProfit;\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def maxProfitAssignment(self, difficulty, profit, worker):\n        max_difficulty = max(difficulty)\n        max_profit_up_to_difficulty = [0] * (max_difficulty + 1)\n\n        for d, p in zip(difficulty, profit):\n            max_profit_up_to_difficulty[d] = max(max_profit_up_to_difficulty[d], p)\n\n        for i in range(1, max_difficulty + 1):\n            max_profit_up_to_difficulty[i] = max(max_profit_up_to_difficulty[i], max_profit_up_to_difficulty[i - 1])\n\n        total_profit = 0\n        for ability in worker:\n            if ability > max_difficulty:\n                total_profit += max_profit_up_to_difficulty[max_difficulty]\n            else:\n                total_profit += max_profit_up_to_difficulty[ability]\n\n        return total_profit\n        \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 maxDifficulty = Math.max(...difficulty);\n    let maxProfitUpToDifficulty = new Array(maxDifficulty + 1).fill(0);\n\n    for (let i = 0; i < difficulty.length; i++) {\n        maxProfitUpToDifficulty[difficulty[i]] = Math.max(maxProfitUpToDifficulty[difficulty[i]], profit[i]);\n    }\n\n    for (let i = 1; i <= maxDifficulty; i++) {\n        maxProfitUpToDifficulty[i] = Math.max(maxProfitUpToDifficulty[i], maxProfitUpToDifficulty[i - 1]);\n    }\n\n    let totalProfit = 0;\n    for (let ability of worker) {\n        if (ability > maxDifficulty) {\n            totalProfit += maxProfitUpToDifficulty[maxDifficulty];\n        } else {\n            totalProfit += maxProfitUpToDifficulty[ability];\n        }\n    }\n\n    return totalProfit;\n};\n```\n![upvote.png](https://assets.leetcode.com/users/images/ae7b6a0f-bc82-4c50-bede-27cdbb032188_1718672884.964757.png)\n
['Array', 'Two Pointers', 'Binary Search', 'Greedy', 'Python', 'C++', 'Java', 'JavaScript']