Most Profit Assigning Work Leetcode Solution
Most Profit Assigning Work Problem Description:
You have n jobs and m workers. You are given three arrays: difficulty, profit, and worker where:
difficulty[i] and profit[i] are the difficulty and the profit of the ith job, and
worker[j] is the ability of the jth worker (i.e., the jth worker can only complete a job with difficulty at most worker[j]).
Every worker can be assigned at most one job, but one job can be completed multiple times.
For example, if three workers attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, their profit is $0.
Return the maximum profit we can achieve after assigning the workers to the jobs.
Examples:
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.
Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0
Explanation: Workers have abilities [40, 25, 25], but the easiest job requires difficulty 47. Since no worker can complete any job, the total profit is 0.
Constraints:
n == difficulty.length
n == profit.length
m == worker.length
1 <= n, m <= 10⁴
1 <= difficulty[i], profit[i], worker[i] <= 10⁵
Brute Force Approach
To approach the problem, we have n jobs and m workers. We are given three arrays: difficulty, profit, and worker, where:
- difficulty[i] and profit[i] represent the difficulty and profit of the ith job.
- worker[j] represents the ability of the jth worker, meaning they can only complete jobs with difficulty ≤ worker[j].
Each of us can assign at most one job to a worker, but the same job can be completed by multiple workers.
Our task is to determine the maximum total profit that we can achieve after optimally assigning the workers to the jobs.
In other words, we need to assign each worker the best possible job they can do so that the total profit is maximized.
For every worker, we must find the most profitable job they can complete. This means finding a job where the difficulty is less than or equal to the worker’s ability (worker[i]).
Since each difficulty[i] has a corresponding profit[i], we can pair them together. Now, for every worker, we need to check all available jobs and find the one that satisfies two conditions:
- The job’s difficulty should be less than or equal to the worker’s ability. This ensures the worker can actually do the job.
- Among all such jobs, pick the one with the highest profit. This ensures the worker is assigned the best possible job.
To do this, we go through all jobs for each worker, check which jobs they can do, and pick the one that gives the most profit. This way, we maximize the total profit earned by all workers.
Let's understand with an example:
Most Profit Assigning Work example:
Let's understand the brute force approach for solving the Most Profit Assigning Work problem with an example:
Input:
difficulty = [2,4,6,8,10]
profit = [10,20,30,40,50]
worker = [4,5,6,7]
Step-by-Step Dry Run:
For each worker, we check all jobs and find the most profitable one they can do:
- Worker = 4 → Can do jobs with difficulty ≤ 4 → Possible jobs: (2 → $10), (4 → $20) → Picks (4 → $20)
- Worker = 5 → Can do jobs with difficulty ≤ 5 → Possible jobs: (2 → $10), (4 → $20) → Picks (4 → $20)
- Worker = 6 → Can do jobs with difficulty ≤ 6 → Possible jobs: (2 → $10), (4 → $20), (6 → $30) → Picks (6 → $30)
- Worker = 7 → Can do jobs with difficulty ≤ 7 → Possible jobs: (2 → $10), (4 → $20), (6 → $30) → Picks (6 → $30)
Total Profit Calculation: 20 + 20 + 30 + 30 = 100
Final Output: 100
Steps to Implement the Solution:
Pair Jobs with Their Profits:
- Create a list of pairs (difficulty, profit).
- This helps in easily accessing job difficulty and corresponding profit together.
Initialize Total Profit:
- Set netProfit = 0 to store the maximum total profit.
Iterate Through Each Worker:
- For each worker[i], find the best job they can do.
- Initialize jobProfit = 0 to keep track of the maximum profit the worker can earn.
Find the Best Job for the Worker:
- Check all jobs (difficulty[i] ≤ worker[i]).
- Among all valid jobs, pick the one with the highest profit.
Update Total Profit:
- Add jobProfit to netProfit.
- Return the Total Maximum Profit.
Below is the solution to the LeetCode problem Most Profit Assigning Work
Most Profit Assigning Work solution / Code Implementation
1. Most Profit Assigning Work solution in C++ Try on Compiler
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
// Get the number of jobs and workers
int n = difficulty.size();
int m = worker.size();
// Create a vector of pairs to store job difficulty and corresponding profit
vector<pair<int, int>> jobProfile;
for(int i = 0; i < n; i++) {
jobProfile.push_back({difficulty[i], profit[i]});
}
// Initialize the total profit to zero
int netProfit = 0;
// Iterate through each worker
for(int i = 0; i < m; i++) {
// Initialize search range for jobs
int l = 0, r = n - 1;
// Variable to store the best job profit for the current worker
int jobProfit = 0;
// Get the ability of the current worker
int ability = worker[i];
// Iterate through all jobs to find the best possible job for the worker
for(int i = l; i <= r; i++) {
// Check if the worker can do the job
if(jobProfile[i].first <= ability)
// Update the maximum profit possible for this worker
jobProfit = max(jobProfit, jobProfile[i].second);
}
// Add the best profit found for this worker to the total profit
netProfit += jobProfit;
}
// Return the total maximum profit
return netProfit;
}
};
2. Most Profit Assigning Work solution in Java Try on Compiler
import java.util.*;
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
// Get the number of jobs and workers
int n = difficulty.length;
int m = worker.length;
// Create a list of pairs to store job difficulty and corresponding profit
List<int[]> jobProfile = new ArrayList<>();
for (int i = 0; i < n; i++) {
jobProfile.add(new int[]{difficulty[i], profit[i]});
}
// Initialize the total profit to zero
int netProfit = 0;
// Iterate through each worker
for (int i = 0; i < m; i++) {
// Initialize search range for jobs
int l = 0, r = n - 1;
// Variable to store the best job profit for the current worker
int jobProfit = 0;
// Get the ability of the current worker
int ability = worker[i];
// Iterate through all jobs to find the best possible job for the worker
for (int j = l; j <= r; j++) {
// Check if the worker can do the job
if (jobProfile.get(j)[0] <= ability)
// Update the maximum profit possible for this worker
jobProfit = Math.max(jobProfit, jobProfile.get(j)[1]);
}
// Add the best profit found for this worker to the total profit
netProfit += jobProfit;
}
// Return the total maximum profit
return netProfit;
}
}
3. Most Profit Assigning Work solution in Python Try on Compiler
class Solution:
def maxProfitAssignment(self, difficulty, profit, worker):
# Get the number of jobs and workers
n = len(difficulty)
m = len(worker)
# Create a list of tuples to store job difficulty and corresponding profit
jobProfile = [(difficulty[i], profit[i]) for i in range(n)]
# Initialize the total profit to zero
netProfit = 0
# Iterate through each worker
for i in range(m):
# Initialize search range for jobs
l, r = 0, n - 1
# Variable to store the best job profit for the current worker
jobProfit = 0
# Get the ability of the current worker
ability = worker[i]
# Iterate through all jobs to find the best possible job for the worker
for j in range(l, r + 1):
# Check if the worker can do the job
if jobProfile[j][0] <= ability:
# Update the maximum profit possible for this worker
jobProfit = max(jobProfit, jobProfile[j][1])
# Add the best profit found for this worker to the total profit
netProfit += jobProfit
# Return the total maximum profit
return netProfit
4. Most Profit Assigning Work solution in Javascript Try on Compiler
var maxProfitAssignment = function(difficulty, profit, worker) {
// Get the number of jobs and workers
let n = difficulty.length;
let m = worker.length;
// Create an array of objects to store job difficulty and corresponding profit
let jobProfile = [];
for (let i = 0; i < n; i++) {
jobProfile.push([difficulty[i], profit[i]]);
}
// Initialize the total profit to zero
let netProfit = 0;
// Iterate through each worker
for (let i = 0; i < m; i++) {
// Initialize search range for jobs
let l = 0, r = n - 1;
// Variable to store the best job profit for the current worker
let jobProfit = 0;
// Get the ability of the current worker
let ability = worker[i];
// Iterate through all jobs to find the best possible job for the worker
for (let j = l; j <= r; j++) {
// Check if the worker can do the job
if (jobProfile[j][0] <= ability)
// Update the maximum profit possible for this worker
jobProfit = Math.max(jobProfit, jobProfile[j][1]);
}
// Add the best profit found for this worker to the total profit
netProfit += jobProfit;
}
// Return the total maximum profit
return netProfit;
};
Complexity Analysis of the problem (brute force)
Time Complexity: O(m * n)
- Creating the Job Profile (Pairing Difficulty and Profit)
We iterate through n jobs to pair each difficulty with its corresponding profit. Time Complexity: O(n) - Finding the Best Job for Each Worker
For each worker (m workers), we iterate through all jobs (n jobs) to find the most profitable one they can do.
This results in a nested loop with a time complexity of O(m * n). - Overall Complexity
Step 1: O(n)
Step 2: O(m * n)
Final Time Complexity: O(m * n)
Space Complexity: O(n+m)
- Auxiliary Space Complexity: O(n)
The algorithm uses a few integer variables. The extra space used is O(n) for the jobProfile vector.
Therefore, the auxiliary space complexity is O(n). - Total Space Complexity: O(n+m)
The total space complexity of the approach is O(n + m), accounting for the input storage of the difficulty, profit, and worker arrays.
Therefore, the total space complexity is O(n+m).
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(m * n), where n is the number of jobs and m is the number of workers (both having an upper limit of 10⁴). In the worst-case scenario, when n and m are at their maximum constraints (10⁴ each), the total number of operations can be as large as 10⁸.
This time complexity can become inefficient when both n and m are large, particularly when n = 10⁴ and m = 10⁴, leading to nearly 10⁸ operations. While this may be feasible for some test cases, it could lead to inefficient execution and exceed time limits for larger inputs.
In competitive programming, the typical acceptable time complexity limit is around 10⁶ operations per test case. Since this solution may perform significantly more operations (10⁸ in the worst case), it may become impractical for large inputs. However, this solution is accepted on LeetCode due to less strict test cases.
How to optimize it?
In the previous approach, we iterated through each worker and checked every possible job they could complete, comparing their ability to each job's difficulty and selecting the one with the maximum profit. This led to a time complexity of O(m * n), where m is the number of workers and n is the number of jobs.
Now, let’s think about improving this approach.
The main issue was that we checked each worker's ability against every possible job, leading to a lot of redundant comparisons. This made the solution inefficient, especially when both the number of workers and jobs were large.
Can we make this part faster?
Yes! Here's the key insight:
We are essentially searching for the maximum profit a worker can earn, which lies between index 0 and index n-1 of the difficulty and profit array. Instead of checking each job individually for every worker, can we limit our search to a smaller range?
Since we are comparing each worker's ability (worker[i]) with every value in the difficulty array (difficulty[i]), can we reduce these operations?
Yes! What if we sort the difficulty array?
If we sort the difficulty array, we can optimize the process. Once we encounter a difficulty[i] that is greater than the worker[i], we know that all subsequent jobs will also have a higher difficulty (since the array is sorted). This allows us to break early and move on to the next worker, reducing unnecessary comparisons and improving efficiency.
Now that we have the difficulty array sorted with the profit array paired accordingly, we can search for the suitable job in this sorted range instead of an unsorted array.
Wait! We need to search in a sorted range — can we apply any technique here?
Yes, we can try binary search.
Let’s check the conditions needed to apply binary search:
- The data structure is sorted:
The difficulty array is sorted, but the profit array is paired with the difficulty, and the pairing may not be sorted. - The middle element helps minimize or maximize the search space:
Since the profit array is not sorted, we don’t know which side of the middle element will give us more profit, making it difficult to apply binary search directly. - The search space is monotonic:
The search space is not monotonic, because while difficulty is sorted, the profit does not guarantee a monotonic behavior that would allow binary search to effectively reduce the search space.
It seems that binary search is not feasible here, but wait, let's observe one thing. Can we make the paired profit array sorted in a way that helps us maximize the profit for every worker?
Yes, we can! Here’s the observation:
Since we are required to maximize profit for each worker, note that the difficulty array is sorted but the profit array is not. This can lead to a situation where a higher difficulty job has a lower profit, and a lower difficulty job has a higher profit. For example, take indices i and j, such that i < j. It’s possible that difficulty[i] < difficulty[j] (since the difficulty array is sorted), but profit[i] > profit[j].
In this case, we can simply replace profit[j] with profit[i] because if a worker is able to do the more difficult job (at index j), they can definitely handle the job at index i. Therefore, it makes sense to ensure that for every index, the profit array is non-decreasing. This guarantees that workers will always get the highest profit possible for the difficulty they can handle.
Real-World Example
Let’s consider an example to understand this concept. Suppose we have the following arrays for difficulty and profit:
- difficulty = [2, 4, 6, 8]
- profit = [10, 20, 15, 25]
Here, the difficulty array is sorted, but the profit array is not. Notice that at index 2, we have difficulty[2] = 6 and profit[2] = 15, which is less than profit[1] = 20 at index 1, even though difficulty[2] > difficulty[1]. This means that for a worker who can handle a difficulty of 6, they could potentially earn more profit (20) by doing a job with a difficulty of 4 instead of 6.
To fix this, we can replace profit[2] with profit[1], ensuring that workers will get the maximum possible profit for any difficulty they can handle. After this update, the profit array becomes [10, 20, 20, 25], which is now non-decreasing.
Now, if a worker has an ability to handle a difficulty of 6, they will earn the profit of 20, which is the maximum available for that difficulty. This approach ensures that workers are always given the most profitable job they can do, maximizing their earnings.
Now let’s check if binary search is applicable:
Since we have sorted the difficulty array and ensured the profit array is non-decreasing, we can use binary search to efficiently find the most profitable job for each worker.
Conditions for binary search:
- The data structure is sorted:
The difficulty array is sorted, and we have made the profit array non-decreasing, so this condition is met. - The search space is monotonic:
The search space for difficulties is monotonic. This means that as we move from lower to higher difficulty levels, the set of jobs that a worker can handle either stays the same or increases. This is important because:
If a worker can do a job with a certain difficulty, they can also do jobs with smaller difficulties (if available in the sorted list), but not the other way around.
If a worker can’t do a job with a certain difficulty, they won’t be able to do any jobs with higher difficulties either.
For example, let’s consider an array of difficulty = [2, 4, 6, 8, 10] and a worker with ability = 6:
The worker can handle jobs with difficulty 2, 4, and 6 but cannot handle jobs with difficulty 8 or 10.
Therefore, once we find the highest difficulty a worker can handle (like 6), we know that they cannot handle any job with a difficulty higher than that. Thus, for binary search, once we find a valid job, we can explore higher difficulty jobs to check if they offer more profit for that worker.
This monotonicity helps us confidently discard ranges of the search space, making the binary search more efficient. - The middle element helps minimize or maximize the search space:
When performing binary search, we start by picking the middle element of the current range. For example, if we are searching through possible difficulty levels for a worker, we check the middle difficulty in the sorted difficulty array to see if a worker can do it. If we can find a job with this difficulty where the worker can earn the highest profit, then we narrow the search space accordingly:
If the middle difficulty works (i.e., the worker can perform the job and earn a profit), we know that we might be able to increase the difficulty further and still get a valid solution. So, we move to the right half of the array, looking for a potentially more difficult and profitable job that the worker can handle.
If the middle difficulty doesn’t work, it means the worker cannot handle that difficulty, and we need to lower the difficulty to find a job that fits. Thus, we move to the left half of the array.
This binary search strategy helps reduce the number of comparisons we need to make, narrowing down the possible difficulty levels quickly.
Binary search can help us quickly find the maximum difficulty each worker can handle while still maximizing their profit.
Most Profit Assigning Work Algorithm
We can use binary search to determine the maximum difficulty level for which a worker can earn the highest profit.
Start by setting low to 0 and high to n - 1 (where n is the length of the difficulty array). In each iteration, calculate the middle index mid = (low + high) / 2. If the difficulty at mid allows the worker to earn a profit, store it as a potential answer and narrow the search space to the right half by setting low = mid + 1. If it doesn't work, move the search to the left half by setting high = mid - 1. Continue this process as long as low <= high. Once the condition breaks (i.e., we can no longer assign a valid job with the current difficulty), the stored answer is returned as the maximum difficulty a worker can handle to earn the highest profit.
For each worker, keep track of the jobProfit they can earn and add it to netProfit. After processing all workers, return netProfit as the total maximum profit.
By using binary search, we efficiently reduce the search space, ensuring that we find the best possible job for each worker. This approach avoids the inefficiencies of checking each job individually for every worker and guarantees that we maximize the total profit.
Let us understand this with a video,
most-profit-assigning-work-Animation Explaination
Let's understand with an example:
Most Profit Assigning Work example:
Let's understand the binary search approach for solving the Most Profit Assigning Work problem with an example
Input:
- difficulty = [2, 4, 6, 8, 10]
- profit = [10, 20, 30, 40, 50]
- worker = [4, 5, 6, 7]
Step-by-Step Dry Run:
- Sorting Jobs: The jobs are already sorted based on difficulty, and we pair difficulty with profit:
jobProfile = [(2, 10), (4, 20), (6, 30), (8, 40), (10, 50)]. - For worker[0] = 4:
low = 0, high = 4 (indices of difficulty).
mid = (0 + 4) / 2 = 2, check difficulty[2] = 6.
Worker’s ability = 4, which is less than 6. So, reduce high to 1.
mid = (0 + 1) / 2 = 0, check difficulty[0] = 2.
Worker’s ability = 4, which is greater than 2. Max profit is profit[0] = 10.
Set low = 1, mid = (1 + 1) / 2 = 1, check difficulty[1] = 4.
Worker’s ability = 4, which is greater than equal to 4. Max profit is profit[0] = 20.
jobProfit = 20, add to netProfit = 20. - For worker[1] = 5:
low = 0, high = 4.
mid = (0 + 4) / 2 = 2, check difficulty[2] = 6.
Worker’s ability = 5, which is less than 6. So, reduce high to 1.
mid = (0 + 1) / 2 = 0, check difficulty[0] = 2.
Worker’s ability = 5, which is greater than 2. Max profit is profit[0] = 10.
Set low = 1, mid = (1 + 1) / 2 = 1, check difficulty[1] = 4.
Worker’s ability = 4, which is greater than equal to 4. Max profit is profit[0] = 20.
jobProfit = 20, add to netProfit = 20 + 20 = 40. - For worker[2] = 6:
low = 0, high = 4.
mid = (0 + 4) / 2 = 2, check difficulty[2] = 6.
Worker’s ability = 6, which is equal to 6. Max profit is profit[2] = 30.
set low = 3, mid = (3 + 4) / 2 = 3, check difficulty[3] = 8.
Worker’s ability = 6, which is less than 8. So, reduce high to 2.
since, low > high, so break
jobProfit = 30, add to netProfit = 40 + 30 = 70. - For worker[3] = 7:
low = 0, high = 4.
mid = (0 + 4) / 2 = 2, check difficulty[2] = 6.
Worker’s ability = 7, which is greater than 6. Max profit is profit[2] = 30.
mid = (3 + 4) / 2 = 3, check difficulty[3] = 8.
Worker’s ability = 7, which is less than 8. So, reduce high to 2.
since, low > high, so break
jobProfit = 30, add to netProfit = 70 + 30 = 100.
Final Output: netProfit = 100 (total profit for all workers).
The maximum profit is 100 by assigning jobs based on their abilities using the binary search approach to optimize the job selection for each worker.
How to code it up:
- Initialize Data Structures:
Create a list of pairs (jobProfile) where each pair contains job difficulty and its corresponding profit. - Sort Jobs:
Sort the jobProfile array based on job difficulty in ascending order. - Update Profits:
Traverse the sorted jobs and update each job's profit to reflect the maximum profit obtainable up to that job (propagate the maximum profit from left to right). - Process Each Worker:
For each worker, initialize l = 0 and r = n - 1 (binary search boundaries).
Use binary search to find the most difficult job that the worker can do (highest difficulty job with a profit the worker can handle). - Calculate Maximum Profit:
For each worker, find the maximum profit they can earn from the available jobs, then accumulate it into the total profit (netProfit). - Return the Result:
After processing all workers, return the accumulated netProfit.
Below is the solution to the LeetCode problem Most Profit Assigning Work
Most Profit Assigning Work solution / Code Implementation
1. Most Profit Assigning Work solution in C++ Try on Compiler
class Solution {
public:
// Function to calculate maximum profit assignment
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
// Number of jobs
int n = difficulty.size();
// Number of workers
int m = worker.size();
// Step 1: Pair each job's difficulty with its corresponding profit
vector<pair<int, int>> jobProfile;
for(int i = 0; i < n; i++) {
jobProfile.push_back({difficulty[i], profit[i]});
}
// Step 2: Sort the jobs based on difficulty
sort(jobProfile.begin(), jobProfile.end());
// Step 3: For each job, update the profit to be the maximum profit obtainable up to that job
for(int i = 0; i < n - 1; i++) {
jobProfile[i + 1].second = max(jobProfile[i].second, jobProfile[i + 1].second);
}
// Initialize total profit
int netProfit = 0;
// Step 4: For each worker, find the maximum profit they can earn
for(int i = 0; i < m; i++) {
// Binary search boundaries
int l = 0, r = n - 1;
// Maximum profit for the current worker's ability
int jobProfit = 0;
// Current worker's ability
int ability = worker[i];
// Step 5: Perform binary search to find the most profitable job the worker can do
while(l <= r) {
int mid = (l + r) / 2;
if(jobProfile[mid].first <= ability) {
// If the worker can perform the job, update the jobProfit
jobProfit = max(jobProfit, jobProfile[mid].second);
// Search for more difficult jobs
l = mid + 1;
} else {
// If the worker cannot perform the job, search for easier jobs
r = mid - 1;
}
}
// Step 6: Add the maximum profit for the worker to the total profit
netProfit += jobProfit;
}
// Return the total profit after assigning jobs to all workers
return netProfit;
}
};
2. Most Profit Assigning Work solution in Java Try on Compiler
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.length; // Number of jobs
int m = worker.length; // Number of workers
// Step 1: Pair each job's difficulty with its corresponding profit
int[][] jobProfile = new int[n][2];
for (int i = 0; i < n; i++) {
jobProfile[i][0] = difficulty[i];
jobProfile[i][1] = profit[i];
}
// Step 2: Sort the jobs based on difficulty
Arrays.sort(jobProfile, (a, b) -> Integer.compare(a[0], b[0]));
// Step 3: For each job, update the profit to be the maximum profit obtainable up to that job
for (int i = 0; i < n - 1; i++) {
jobProfile[i + 1][1] = Math.max(jobProfile[i][1], jobProfile[i + 1][1]);
}
int netProfit = 0; // Initialize total profit
// Step 4: For each worker, find the maximum profit they can earn
for (int i = 0; i < m; i++) {
// Binary search boundaries
int l = 0, r = n - 1;
// Maximum profit for the current worker's ability
int jobProfit = 0;
// Current worker's ability
int ability = worker[i];
// Step 5: Perform binary search to find the most profitable job the worker can do
while (l <= r) {
int mid = (l + r) / 2;
if (jobProfile[mid][0] <= ability) {
jobProfit = Math.max(jobProfit, jobProfile[mid][1]);
// Search for more difficult jobs
l = mid + 1;
} else {
// Search for easier jobs
r = mid - 1;
}
}
// Step 6: Add the maximum profit for the worker to the total profit
netProfit += jobProfit;
}
// Return the total profit after assigning jobs to all workers
return netProfit;
}
}
3. Most Profit Assigning Work solution in Python Try on Compiler
class Solution:
def maxProfitAssignment(self, difficulty, profit, worker):
n = len(difficulty) # Number of jobs
m = len(worker) # Number of workers
# Step 1: Pair each job's difficulty with its corresponding profit
jobProfile = [(difficulty[i], profit[i]) for i in range(n)]
# Step 2: Sort the jobs based on difficulty
jobProfile.sort()
# Step 3: For each job, update the profit to be the maximum profit obtainable up to that job
for i in range(n - 1):
jobProfile[i + 1] = (jobProfile[i + 1][0], max(jobProfile[i][1], jobProfile[i + 1][1]))
netProfit = 0 # Initialize total profit
# Step 4: For each worker, find the maximum profit they can earn
for ability in worker:
l, r = 0, n - 1 # Binary search boundaries
jobProfit = 0 # Maximum profit for the current worker's ability
# Step 5: Perform binary search to find the most profitable job the worker can do
while l <= r:
mid = (l + r) // 2
if jobProfile[mid][0] <= ability:
jobProfit = max(jobProfit, jobProfile[mid][1])
l = mid + 1 # Search for more difficult jobs
else:
r = mid - 1 # Search for easier jobs
# Step 6: Add the maximum profit for the worker to the total profit
netProfit += jobProfit
# Return the total profit after assigning jobs to all workers
return netProfit
4. Most Profit Assigning Work solution in Javascript Try on Compiler
var maxProfitAssignment = function(difficulty, profit, worker) {
let n = difficulty.length; // Number of jobs
let m = worker.length; // Number of workers
// Step 1: Pair each job's difficulty with its corresponding profit
let jobProfile = [];
for (let i = 0; i < n; i++) {
jobProfile.push([difficulty[i], profit[i]]);
}
// Step 2: Sort the jobs based on difficulty
jobProfile.sort((a, b) => a[0] - b[0]);
// Step 3: For each job, update the profit to be the maximum profit obtainable up to that job
for (let i = 0; i < n - 1; i++) {
jobProfile[i + 1][1] = Math.max(jobProfile[i][1], jobProfile[i + 1][1]);
}
let netProfit = 0; // Initialize total profit
// Step 4: For each worker, find the maximum profit they can earn
for (let i = 0; i < m; i++) {
let l = 0, r = n - 1; // Binary search boundaries
let jobProfit = 0; // Maximum profit for the current worker's ability
let ability = worker[i]; // Current worker's ability
// Step 5: Perform binary search to find the most profitable job the worker can do
while (l <= r) {
let mid = Math.floor((l + r) / 2);
if (jobProfile[mid][0] <= ability) {
jobProfit = Math.max(jobProfit, jobProfile[mid][1]);
l = mid + 1; // Search for more difficult jobs
} else {
r = mid - 1; // Search for easier jobs
}
}
// Step 6: Add the maximum profit for the worker to the total profit
netProfit += jobProfit;
}
// Return the total profit after assigning jobs to all workers
return netProfit;
};
Complexity Analysis of the problem (binary search)
Time Complexity: O((n + m) log n)
Let's break down the time complexity of the solution:
- Initializing Data Structures:
The creation of the jobProfile list (pairing job difficulties and profits) takes O(n) time, where n is the number of jobs. - Sorting Jobs:
Sorting the jobProfile array based on difficulty takes O(n log n) time. - Updating Profits:
Traversing the sorted jobs to update profits (propagate maximum profit from left to right) takes O(n) time. - Processing Each Worker:
For each worker, we perform a binary search on the sorted jobs. The binary search runs in O(log n) time.
Since there are m workers, processing all workers will take O(m log n) time. - Calculating Maximum Profit:
The total profit calculation involves looping over all workers, which takes O(m) time. - Total Time Complexity:Here, n is the number of jobs and m is the number of workers
Combining all the steps, the total time complexity is:
O(n log n) + O(m log n), which simplifies to O((n + m) log n).
Space Complexity: O(n+m)
- Auxiliary Space Complexity: O(n)
The only significant extra space used is for the jobProfile array, which is O(n). Therefore, the auxiliary space complexity is O(n). - Total Space Complexity: O(n+m)
The input arrays difficulty, profit, and worker each have a size of n and m, respectively. So the input space is O(n + m).
Therefore, the total space complexity is O(n+m).
Is there any scope for further optimizations?
In the previous approach, we iterated through each worker and searched for the most suitable job they could complete by comparing their ability with each job's difficulty. To optimize the search, we used binary search, allowing us to efficiently find the highest difficulty a worker can handle while maximizing their profit. While this approach is significantly faster than a brute-force method, it still has a time complexity of O(m * log n), where m is the number of workers and n is the number of jobs.
Can we optimize it even further?
Alright, let’s take a step back and think. We’ve already optimized our brute-force approach by introducing binary search, bringing the complexity down to O(m * log n). That’s great! But what if I told you we could do even better?
What’s the bottleneck now?
Think about it—we are sorting the jobs based on difficulty and then, for every worker, using binary search to find the most difficult job they can do. This means each worker still goes through a log n search process, which adds up when there are a lot of workers.
So, the question is:
Can we get rid of this binary search and make it even faster?
Let’s break it down:
- What are we doing for each worker? We are finding the hardest job they can do.
- What if we could track the best job as we go instead of searching for it every time?
- What if, instead of searching from scratch for every worker, we just move forward through the jobs as needed?
Let’s imagine we have both jobs and workers sorted in increasing order. Now, instead of jumping around with binary search, we can simply process everything in a single pass.
Think of it like this:
- You have two lists—one with sorted job difficulties and another with sorted worker abilities.
- You’re standing at the first job, and workers start arriving one by one.
- If the worker can handle the current job, you update the best profit and move forward to the next job.
- If the worker can’t handle the next job, no problem! Just assign them the best job they could have managed so far.
- Since both lists are sorted, you never need to go back—you just keep moving forward, ensuring every worker gets the best job available.
This way, instead of searching separately for every worker, we process both lists in one sweep. Each job and worker is visited only once, making the solution O(n + m) instead of O(m * log n).
And that’s it! By simply sorting both lists and using a two-pointer approach, we eliminate unnecessary work and make the solution blazing fast!
How to do it?
Now that we understand why the two-pointer approach works let’s break it down into steps to implement it efficiently.
- Sort the Inputs
Since we want to process both jobs and workers in a single pass, we need them to be sorted. Sort the jobs based on difficulty (increasing order). Sort the workers in increasing order as well. - Initialize Pointers and Track Maximum Profit
Use two pointers:
One for the job list (let’s call it j), starting from 0.
One for iterating over the workers.
Keep track of the best profit so far (jobProfit). - Iterate Over Workers and Assign Jobs
For each worker, check if they can handle the job at jobProfile[j].
If they can, update jobProfit with the job's profit and move to the next job.
If they can’t, that means they should take the best job they’ve seen so far. - Accumulate the Total Profit
For each worker, add their best possible job profit to netProfit.
Since we process both lists once, this takes O(n + m) time. - Final Thought:
Instead of searching for a job for every worker, we move forward together through both lists, keeping track of the best job we’ve seen.
This makes the approach significantly faster and removes the need for binary search!
Let us understand this with a video,
Let's understand with an example:
Most Profit Assigning Work example:
Let's understand the two-pointer approach for solving the Most Profit Assigning Work problem with an example
Input:
difficulty = [2, 4, 6, 8, 10]
profit = [10, 20, 30, 40, 50]
worker = [4, 5, 6, 7]
Step 1: Sort the Inputs
difficulty (sorted): [2, 4, 6, 8, 10]
profit (sorted based on difficulty): [10, 20, 30, 40, 50]
worker (sorted): [4, 5, 6, 7]
Step 2: Initialize Pointers and Track Maximum Profit
jobPointer (j) = 0
maxProfit = 0
netProfit = 0
Step 3: Iterate Over Workers and Assign Jobs
Worker 1: Ability = 4
- Check job at jobPointer = 0: difficulty[0] = 2 (worker can do this job) → maxProfit = max(0, 10) = 10
- Check job at jobPointer = 1: difficulty[1] = 4 (worker can do this job) → maxProfit = max(10, 20) = 20
- Check job at jobPointer = 2: difficulty[2] = 6 (worker cannot do this job) → Stop here
- Add maxProfit (20) to netProfit → netProfit = 20
Worker 2: Ability = 5
- Check job at jobPointer = 2: difficulty[2] = 6 (worker cannot do this job) → Stop here
- Add maxProfit (20) to netProfit → netProfit = 40
Worker 3: Ability = 6
- Check job at jobPointer = 2: difficulty[2] = 6 (worker can do this job) → maxProfit = max(20, 30) = 30
- Check job at jobPointer = 3: difficulty[3] = 8 (worker cannot do this job) → Stop here
- Add maxProfit (30) to netProfit → netProfit = 70
Worker 4: Ability = 7
- Check job at jobPointer = 3: difficulty[3] = 8 (worker cannot do this job) → Stop here
- Add maxProfit (30) to netProfit → netProfit = 100
Step 4: Return the Result
- After processing all workers, netProfit = 100.
Final Output: netProfit = 100.
Steps to Implement the Solution:
Here are the generic steps to code the solution concisely:
- Input Parsing:
Take the input arrays: difficulty, profit, and worker. - Create Job Profiles:
Pair each job's difficulty with its corresponding profit.
Use a data structure (like a list or array) to store these pairs. - Sort Jobs:
Sort the job profiles by difficulty in ascending order. - Sort Workers:
Sort the worker array by their abilities. - Initialize Variables:
Initialize netProfit to store the total profit.
Initialize jobProfit to track the maximum profit for jobs workers can do.
Use a pointer j to iterate through the jobs. - Iterate Over Workers:
For each worker:
Compare the worker’s ability with the job difficulties.
Use a pointer j to check jobs the worker can do.
Track the maximum profit the worker can earn by moving through the jobs. - Update Profit:
Add the jobProfit for each worker to the total netProfit. - Return Result:
After processing all workers, return the accumulated netProfit.
Below is the solution to the LeetCode problem Most Profit Assigning Work
Most Profit Assigning Work solution / Code Implementation
1. Most Profit Assigning Work solution in c++ Try on Compiler
class Solution {
public:
// Function to calculate maximum profit assignment for workers
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
// Step 1: Get the number of jobs (n) and workers (m)
int n = difficulty.size();
int m = worker.size();
// Step 2: Create a vector of pairs to store job difficulty and corresponding profit
vector<pair<int, int>> jobProfile(n);
// Step 3: Populate the jobProfile with difficulty and profit pairs
for(int i=0; i<n; i++) {
jobProfile[i] = {difficulty[i], profit[i]};
}
// Step 4: Sort the jobProfile array by difficulty (ascending order)
sort(jobProfile.begin(), jobProfile.end());
// Step 5: Sort the worker array by worker abilities
sort(worker.begin(), worker.end());
// Step 6: Initialize variables for tracking net profit and the maximum profit for each worker
int netProfit = 0;
int jobProfit = 0;
int j = 0;
// Step 7: Iterate through each worker's ability
for(int i=0; i < m; i++) {
int ability = worker[i];
// Step 8: Find the most suitable job for the current worker using two-pointer technique
while(j<n && ability >= jobProfile[j].first) {
// Update jobProfit with the maximum profit available for jobs worker can handle
jobProfit = max(jobProfit, jobProfile[j].second);
j++;
}
// Step 9: Add the maximum profit the worker can earn to the total net profit
netProfit += jobProfit;
}
// Step 10: Return the total accumulated net profit
return netProfit;
}
};
2. Most Profit Assigning Work solution in Java Try on Compiler
class Solution {
// Function to calculate maximum profit assignment for workers
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
// Step 1: Get the number of jobs (n) and workers (m)
int n = difficulty.length;
int m = worker.length;
// Step 2: Create an array of pairs to store job difficulty and corresponding profit
int[][] jobProfile = new int[n][2];
// Step 3: Populate the jobProfile with difficulty and profit pairs
for (int i = 0; i < n; i++) {
jobProfile[i][0] = difficulty[i];
jobProfile[i][1] = profit[i];
}
// Step 4: Sort the jobProfile array by difficulty (ascending order)
Arrays.sort(jobProfile, (a, b) -> a[0] - b[0]);
// Step 5: Sort the worker array by worker abilities
Arrays.sort(worker);
// Step 6: Initialize variables for tracking net profit and the maximum profit for each worker
int netProfit = 0;
int jobProfit = 0;
int j = 0;
// Step 7: Iterate through each worker's ability
for (int i = 0; i < m; i++) {
int ability = worker[i];
// Step 8: Find the most suitable job for the current worker using two-pointer technique
while (j < n && ability >= jobProfile[j][0]) {
// Update jobProfit with the maximum profit available for jobs worker can handle
jobProfit = Math.max(jobProfit, jobProfile[j][1]);
j++;
}
// Step 9: Add the maximum profit the worker can earn to the total net profit
netProfit += jobProfit;
}
// Step 10: Return the total accumulated net profit
return netProfit;
}
}
3. Most Profit Assigning Work solution in Python Try on Compiler
class Solution:
# Function to calculate maximum profit assignment for workers
def maxProfitAssignment(self, difficulty, profit, worker):
# Step 1: Get the number of jobs (n) and workers (m)
n = len(difficulty)
m = len(worker)
# Step 2: Create a list of tuples to store job difficulty and corresponding profit
jobProfile = [(difficulty[i], profit[i]) for i in range(n)]
# Step 3: Sort the jobProfile list by difficulty (ascending order)
jobProfile.sort()
# Step 4: Sort the worker list by worker abilities
worker.sort()
# Step 5: Initialize variables for tracking net profit and the maximum profit for each worker
netProfit = 0
jobProfit = 0
j = 0
# Step 6: Iterate through each worker's ability
for ability in worker:
# Step 7: Find the most suitable job for the current worker using two-pointer technique
while j < n and ability >= jobProfile[j][0]:
# Update jobProfit with the maximum profit available for jobs worker can handle
jobProfit = max(jobProfit, jobProfile[j][1])
j += 1
# Step 8: Add the maximum profit the worker can earn to the total net profit
netProfit += jobProfit
# Step 9: Return the total accumulated net profit
return netProfit
4. Most Profit Assigning Work solution in Javascript Try on Compiler
/**
* @param {number[]} difficulty
* @param {number[]} profit
* @param {number[]} worker
* @return {number}
*/
var maxProfitAssignment = function(difficulty, profit, worker) {
// Step 1: Get the number of jobs (n) and workers (m)
let n = difficulty.length;
let m = worker.length;
// Step 2: Create an array of pairs to store job difficulty and corresponding profit
let jobProfile = [];
for (let i = 0; i < n; i++) {
jobProfile.push([difficulty[i], profit[i]]);
}
// Step 3: Sort the jobProfile array by difficulty (ascending order)
jobProfile.sort((a, b) => a[0] - b[0]);
// Step 4: Sort the worker array by worker abilities
worker.sort((a, b) => a - b);
// Step 5: Initialize variables for tracking net profit and the maximum profit for each worker
let netProfit = 0;
let jobProfit = 0;
let j = 0;
// Step 6: Iterate through each worker's ability
for (let i = 0; i < m; i++) {
let ability = worker[i];
// Step 7: Find the most suitable job for the current worker using two-pointer technique
while (j < n && ability >= jobProfile[j][0]) {
// Update jobProfit with the maximum profit available for jobs worker can handle
jobProfit = Math.max(jobProfit, jobProfile[j][1]);
j++;
}
// Step 8: Add the maximum profit the worker can earn to the total net profit
netProfit += jobProfit;
}
// Step 9: Return the total accumulated net profit
return netProfit;
};
Complexity Analysis of the problem (two pointers)
Time Complexity: O(n log n + m log m)
The time complexity analysis for this approach is as follows:
- Sorting the job profiles:
Sorting the difficulty and profit arrays takes O(n log n) time, where n is the number of jobs.
Sorting the worker array takes O(m log m) time, where m is the number of workers. - Iterating through the workers:
For each worker, we iterate through the jobs array using a pointer j. The pointer j moves forward through the jobs only once, meaning that in total, it will process each job at most once.
This gives us O(n) operations to check all jobs for all workers, where n is the number of jobs. - Final complexity:
Sorting the job profile array takes O(n log n).
Sorting the worker array takes O(m log m).
The two-pointer iteration through the workers and jobs takes O(n + m), as each job and worker are processed only once.
Thus, the overall time complexity of this approach is: O(n log n + m log m + n)
Which simplifies to: O(n log n + m log m)
This is the total time complexity for the solution.
Space Complexity: O(n + m)
- Auxiliary Space Complexity: O(n)
The most significant extra space used is the jobProfile array, which stores pairs of difficulty and profit. This array has a size of n (the number of jobs).
Therefore, the auxiliary space is O(n) for storing the jobProfile array. - Total Space Complexity: O(n + m)
The input arrays are: difficulty, profit, and worker. Each of these arrays requires O(n) or O(m) space, where n is the number of jobs and m is the number of workers.
Therefore, the total space complexity is O(n + m), considering both the input and auxiliary space.
Similar Problems
To efficiently solve this problem, we can leverage key techniques such as array manipulation, the two pointers technique, and a greedy approach. By first sorting the difficulty and profit arrays together, we can naturally align job complexities with their respective rewards. Using the two pointers technique, we can efficiently match each worker's ability to the most profitable job they can complete. This method ensures we maximize profit while iterating through the sorted arrays in linear time. The greedy strategy comes into play by always assigning a worker to the highest-paying feasible job, ensuring optimal profit accumulation. Combining these techniques allows for a clean, efficient solution to maximize the total profit earned by all workers.
To solve this problem efficiently, we can utilize sorting and binary search. By sorting the jobs based on their difficulty and sorting the workers by their abilities, we create a structured order that simplifies job assignment. Using binary search, we can quickly identify the most profitable job that a worker can handle, significantly reducing the time complexity compared to a linear search approach. This combination of sorting and binary search ensures both efficiency and correctness in maximizing the total profit.
Now we have successfully tackled this problem, let's try these similar problems.
You have n tasks and m workers. Each task has a strength requirement stored in a 0-indexed integer array tasks, with the ith task requiring tasks[i] strength to complete. The strength of each worker is stored in a 0-indexed integer array workers, with the jth worker having workers[j] strength. Each worker can only be assigned to a single task and must have a strength greater than or equal to the task's strength requirement (i.e., workers[j] >= tasks[i]).
Additionally, you have pills magical pills that will increase a worker's strength by strength. You can decide which workers receive the magical pills, however, you may only give each worker at most one magical pill.
Given the 0-indexed integer arrays tasks and workers and the integers pills and strength, return the maximum number of tasks that can be completed.
You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.
You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.
Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.
You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.
The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.
Return the maximum number of matchings between players and trainers that satisfy these conditions