Easy Java Solution | Greedy | Beats 100 💯✅
maxProfitAssignment\n\n## Problem Statement\nGiven three arrays difficulty, profit, and worker, where:\n- difficulty[i] represents the difficulty of the i-th jo
# maxProfitAssignment\n\n## Problem Statement\nGiven three arrays `difficulty`, `profit`, and `worker`, where:\n- `difficulty[i]` represents the difficulty of the `i-th` job.\n- `profit[i]` represents the profit of the `i-th` job.\n- `worker[j]` represents the ability of the `j-th` worker.\n\nThe task is to assign each worker a job such that the worker\'s ability is at least as great as the job\'s difficulty and to maximize the total profit. If a worker cannot complete any job, they earn zero profit.\n\nThe goal is to calculate the maximum total profit that can be obtained.\n\n## Intuition\n1. **Understand the Relationship Between Job and Worker**:\n   - Each job has a certain difficulty and offers a specific profit.\n   - Each worker has an ability, and they can only perform jobs that match or are less difficult than their ability.\n   - To maximize the profit for each worker, they should be assigned the most profitable job that they can handle based on their ability.\n\n2. **Preprocess Jobs for Quick Lookup**:\n   - Create a list to store the maximum profit obtainable for any given difficulty up to the maximum difficulty. This will help in efficiently finding the best possible job for each worker.\n\n3. **Efficiently Assign Jobs to Workers**:\n   - By using a precomputed list of maximum profits up to each difficulty, the profit for each worker can be determined in constant time.\n\n## Approach\n1. **Determine Maximum Difficulty**:\n   - Traverse the `difficulty` array to find the maximum job difficulty. This will define the size of our profit lookup table.\n\n2. **Construct Profit Lookup Table**:\n   - Create an array `maxProfitUpToDifficulty` where each index represents a difficulty level, and the value at each index represents the maximum profit obtainable for that difficulty.\n   - Iterate over the `difficulty` and `profit` arrays to fill in the maximum profit for each specific job difficulty.\n\n3. **Fill in the Maximum Profits**:\n   - Ensure that for each difficulty level, the profit is the maximum available up to that difficulty by propagating the highest profit found so far to subsequent difficulties.\n\n4. **Calculate Total Profit for Workers**:\n   - For each worker, use their ability to directly look up the best possible profit they can achieve from the `maxProfitUpToDifficulty` array.\n   - Sum up the profits to get the total profit.\n\n## Complexity Analysis\n- **Time Complexity**:\n  - **Finding Maximum Difficulty**: \\(O(n)\\) where \\(n\\) is the number of jobs.\n  - **Constructing the Profit Lookup Table**: \\(O(n)\\), as it involves a single scan over the jobs and another scan up to the maximum difficulty.\n  - **Calculating Total Profit**: \\(O(m)\\) where \\(m\\) is the number of workers, as each worker\'s best possible job is found in constant time.\n  - **Total**: \\(O(n + m + D)\\), where \\(D\\) is the maximum difficulty.\n\n- **Space Complexity**:\n  - The primary additional space used is for the `maxProfitUpToDifficulty` array, which is proportional to the maximum difficulty.\n  - **Total**: \\(O(D)\\), where \\(D\\) is the maximum difficulty.\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
['Array', 'Math', 'Greedy', 'Java']