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, andworker[j] is the ability of 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.
$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.
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.lengthn == profit.lengthm == worker.length1 <= n, m <= 1041 <= difficulty[i], profit[i], worker[i] <= 105In #826 Most Profit Assigning Work, each job has a difficulty and a corresponding profit, while each worker has a maximum ability. The goal is to assign workers to jobs they can complete and maximize the total profit. Multiple workers can take the same job.
A common approach is to sort jobs by difficulty and sort workers by ability. Using a two-pointer greedy strategy, iterate through workers and keep track of the best profit available among all jobs with difficulty less than or equal to the worker’s ability. This allows you to efficiently assign the most profitable achievable job to each worker.
Another variant uses binary search on sorted difficulties with a prefix maximum profit array. Both strategies rely on preprocessing the job list so that profit values are non-decreasing with difficulty. The dominant cost comes from sorting the arrays, leading to an overall time complexity of O(n log n + m log m) (or O(n log n + m log n) with binary search) and O(1) to O(n) extra space depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Two Pointers (Greedy) | O(n log n + m log m) | O(1) |
| Sorting + Binary Search with Prefix Max Profit | O(n log n + m log n) | O(n) |
codestorywithMIK
In this approach, we sort both jobs by difficulty and workers by their ability. We then iterate over each worker and find the highest profit job they can perform using a greedy approach.
First, we pair each job's difficulty with its profit and then sort these pairs by difficulty. We also sort the worker array. Next, for each worker, we iterate through the sorted job list and keep track of the maximum profit the worker can obtain, given that their ability must be greater than or equal to the job's difficulty. This ensures that each worker is assigned the most profitable job they can perform, thus maximizing the total profit.
Time Complexity: O(n log n + m log m)
Space Complexity: O(n)
1#include <stdio.h>
2#include <stdlib.h>
3
4int compareJobs(const void *a, const void *b) {
The solution first sorts the jobs based on their difficulty and profits, and then sorts the workers based on their ability. It uses a while loop to traverse through eligible jobs for each worker and tracks the maximum profit they can make, which is then added to the total profit.
This approach improves efficiency by preparing the job list in advance for profit maximization, and processes each worker in one pass. The basic idea is to preprocess the jobs to track the maximum profit obtainable up to each difficulty level. We create a running maximum profit and apply this to each worker based on their ability directly.
First, jobs are paired and sorted by difficulty; then, as we iterate through them, we constantly update the maximum profit obtainable up to each job's difficulty. When assessing workers, we simply apply their ability to this precomputed list to find the applicable maximum profit, ensuring minimal lookups and passing through the sorted jobs just once.
Time Complexity: O(n log n + m log m)
Space Complexity: O(n)
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, after sorting jobs by difficulty, you can precompute the maximum profit up to each difficulty. For each worker, binary search finds the hardest job they can handle, and the stored prefix maximum gives the best profit.
Yes, variations of this problem appear in coding interviews at large tech companies. It tests understanding of greedy strategies, sorting, and efficient searching techniques, which are common interview themes.
The optimal approach sorts jobs by difficulty and workers by ability, then uses a greedy two-pointer scan. While iterating through workers, you maintain the maximum profit among jobs they can perform and add it to the total. This avoids checking every job for every worker.
Arrays combined with sorting are typically sufficient for this problem. A prefix maximum array or a running variable can track the best profit seen so far. Some solutions also use binary search over sorted difficulties for efficient lookups.
This C implementation sorts jobs and workers, and computes a running maximum profit for each difficulty level. The logic uses these precomputed profits to quickly sum the maximum applicable profits for each worker in a single iteration.