
Problem Statement
In this problem, you are provided with information about n
different jobs and m
workers. Each job has a specific difficulty and profit associated with it, represented by the arrays difficulty
and profit
. Each worker has a maximum job difficulty they can handle, given by the array worker
.
To summarize the interaction:
difficulty[i]
andprofit[i]
represent the difficulty and the profit of thei-th
job, respectively.worker[j]
represents the difficulty limit up to which thej-th
worker can handle a job.
You have to assign jobs to each worker such that the worker can manage the difficulty of the assigned job. Each worker can only take one job but the same job can be taken by more than one worker, thereby multiplying its profit contribution depending on how many workers take it.
Your goal is to find out the maximum total profit you can achieve by making optimal job assignments based on the workers’ capabilities.
Key Details:
- A job can be repeated among workers.
- If there is no suitable job for a worker due to difficulty constraints, that worker's contribution to profit is
0
. - The relationship between difficulty, profit, and workers' capabilities determines the optimal assignment for maximum profit.
Examples
Example 1
Input:
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output:
100
Explanation:
Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
Example 2
Input:
difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output:
0
Constraints
n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 104
1 <= difficulty[i], profit[i], worker[i] <= 105
Approach and Intuition
To solve this problem efficiently, follow these steps:
Prepare the job list with enhanced information:
- Combine the job
difficulty
andprofit
into a combined list of tuples(difficulty, profit)
. - Sort this list primarily by difficulty.
- Combine the job
Optimize access to the maximum profit for a given difficulty:
- For each difficulty level (from the sorted list), keep track of the maximum profit so far, ensuring you can quickly determine the highest possible profit for a given or lower difficulty.
Handle each worker:
- For each worker, identify the job with the highest profit they can perform, constrained by their capability (
worker[j]
). - Sort the
worker
array to efficiently match workers to jobs.
- For each worker, identify the job with the highest profit they can perform, constrained by their capability (
Calculate the total profit:
- Traverse through each worker's capacity and match it to the best job they can take by making use of previously calculated maximum profits for any difficulty level up to their maximum capability.
- Sum the profits derived from optimal assignments to get the total maximum profit.
Rationale:
- Sorting and preprocessing the jobs by difficulty helps in reducing the time complexity when assigning the jobs to workers, as we can avoid repeatedly searching for suitable jobs for each worker.
- Maintaining a running maximum profit for each difficulty level allows for quick look-up of the best job a worker can handle.
- As constraints allow up to 10,000 workers and jobs, this approach makes the problem manageable within competitive time limits, aiming for efficiency particularly in how we traverse and access job profits and difficulties relative to each worker’s capacity.
Solutions
- C++
- Java
- Python
class Solution {
public:
int calculateMaximumProfit(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int highestSkill = *max_element(worker.begin(), worker.end());
vector<int> jobProfit(highestSkill + 1, 0);
for (int i = 0; i < difficulty.size(); i++) {
if (difficulty[i] <= highestSkill)
jobProfit[difficulty[i]] = max(jobProfit[difficulty[i]], profit[i]);
}
for (int i = 1; i <= highestSkill; i++)
jobProfit[i] = max(jobProfit[i], jobProfit[i - 1]);
int totalProfit = 0;
for (auto skill : worker) {
int profitAtSkill = jobProfit[skill];
totalProfit += profitAtSkill;
}
return totalProfit;
}
};
This C++ solution tackles the problem of determining the maximum profit from assigning jobs based on their difficulty, profit, and the skills of the workers. The calculateMaximumProfit
function starts by identifying the maximum skill level among the workers using max_element
. It initializes a jobProfit
vector the size of the highest skill plus one, with all values set to zero.
Here's the approach taken:
- Iterate through each job:
- If the job's difficulty is less than or equal to the highest skill, update the corresponding index in the
jobProfit
vector with the maximum profit achievable for that difficulty.
- If the job's difficulty is less than or equal to the highest skill, update the corresponding index in the
- Modify the
jobProfit
vector so thatjobProfit[i]
always represents the maximum profit that can be obtained with skill leveli
or less. This handles cases where there might be several jobs of varying difficulties but identical skill levels. - Calculate the total profit by iterating through each worker's skill and summing up the maximum profit obtainable for each skill level from the previously populated
jobProfit
vector.
This solution ensures that each worker is assigned the job with the highest profit possible according to their skill sets without exceeding the worker's level of difficulty, leading to an optimization of the total profit from all assignments.
class Solution {
public int findMaxProfit(
int[] difficulty,
int[] profit,
int[] worker
) {
int highestSkill = Arrays.stream(worker).max().getAsInt();
int[] taskProfits = new int[highestSkill + 1];
for (int i = 0; i < difficulty.length; i++) {
if (difficulty[i] <= highestSkill) {
taskProfits[difficulty[i]] = Math.max(taskProfits[difficulty[i]], profit[i]);
}
}
for (int i = 1; i <= highestSkill; i++) {
taskProfits[i] = Math.max(taskProfits[i], taskProfits[i - 1]);
}
int totalProfit = 0;
for (int skill : worker) {
totalProfit += taskProfits[skill];
}
return totalProfit;
}
}
This Java solution tackles the problem of determining the most profit from assigning work based on differing worker skills and task difficulties. Take the following steps to understand the code's approach:
Calculate the maximum skill level among all workers. This helps in setting the size for the
taskProfits
array that will store the highest possible profit for each skill level up to the highest worker's skill.Initialize an array,
taskProfits
, to record the best profit obtainable for each difficulty level up to the maximum skill level found.Loop through each task defined by arrays
difficulty
andprofit
. For tasks within the skill range of at least one worker, update the corresponding index in thetaskProfits
array with the maximum profit for that difficulty level.Traverse the
taskProfits
array from beginning to end. Ensure that each position holds the maximum profit up to that difficulty level, enabling workers with higher skill levels to achieve more profit from simpler tasks if those simpler tasks offer higher compensation.Finally, sum up the profits for each worker based on their skill levels using the
taskProfits
information. Workers will earn the best profit for their skill level, irrespective of the individual task difficulties they can handle.
This approach efficiently calculates total profits using dynamic programming concepts, ensuring optimal profit assignment for a given set of workers and tasks.
class Solution:
def calculateMaxProfit(
self, skillLevels: List[int], earnings: List[int], employees: List[int]
) -> int:
maxSkill = max(employees)
taskDifficulty = [0] * (maxSkill + 1)
for index in range(len(skillLevels)):
if skillLevels[index] <= maxSkill:
taskDifficulty[skillLevels[index]] = max(taskDifficulty[skillLevels[index]], earnings[index])
for j in range(1, maxSkill + 1):
taskDifficulty[j] = max(taskDifficulty[j], taskDifficulty[j - 1])
totalProfit = 0
for skill in employees:
totalProfit += taskDifficulty[skill]
return totalProfit
This Python solution tackles the problem of maximizing profit from assigning work based on skill levels and corresponding earnings. The function calculateMaxProfit
takes three parameters: skillLevels
, earnings
, and employees
. Here's a breakdown of how the code operates:
- Calculate the highest skill level among the employees to ensure that task assignments cater to the highest possible skill level present.
- Initiate a list
taskDifficulty
where its indices represent skill levels and values represent the maximum earning potential for that skill level. - Populate the
taskDifficulty
list such that each skill level has the maximum earnings it can yield without exceeding the specific skill. This is achieved by iterating through the givenskillLevels
andearnings
. - Iterate from the lowest to the highest skill levels to fill out any gaps in
taskDifficulty
. This ensures that for any skill level without direct corresponding earnings, the best possible undervalued task is assigned. - Initialize
totalProfit
. Iterate over each employee's skill level to accumulate potential earnings based on the populatedtaskDifficulty
. - Finally, return
totalProfit
, representing the maximum profit derived from optimally assigned tasks based on employee skills.
This approach efficiently maps tasks to skills, ensuring that every employee's skill is utilized to its utmost profit potential while preserving the complexity of O(N) with respect to the number of employees and their skill distribution.
No comments yet.