Most Profit Assigning Work — Solution in Python, Java & C++
Most Profit Assigning Work solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Most Profit Assigning Work is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Zoho interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Two Pointers
- Asked at: Amazon, Google, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Job i has difficulty difficulty[i] and pays profit[i]. Worker j can take any job whose difficulty is at most worker[j].
Each worker takes at most one job, but a job may be taken by any number of workers (or none). Return the maximum total profit.
Example 1
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: The workers earn 20, 20, 30 and 30.
Example 2
Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0
Explanation: No worker is strong enough for any job.
Example 3
Input: difficulty = [1,1,1], profit = [5,3,9], worker = [2]
Output: 9
Explanation: The worker picks the best of the three equally easy jobs.
Constraints
1 <= difficulty.length == profit.length <= 100001 <= worker.length <= 100001 <= difficulty[i], profit[i], worker[j] <= 100000
Hints for Most Profit Assigning Work
Hint 1
Each worker independently wants the highest-paying job they can do — there is no competition for jobs.
Hint 2
Sort the jobs by difficulty and the workers by strength, then sweep both together.
Hint 3
Keep a running maximum of the profit among jobs already admitted; a stronger worker can only do more.
How to solve Most Profit Assigning Work
Because a job can be taken any number of times, each worker's choice is independent: take the most profitable job within reach. Sorting both lists lets a single pointer accumulate the best profit reachable as the workers get stronger.
Approach
- Pair each difficulty with its profit and sort the pairs by difficulty.
- Sort the workers ascending.
- For each worker, advance the job pointer over every job they can do, keeping
best, the maximum profit seen so far. - Add
bestto the total.
Why it works
best is the maximum profit over all jobs of difficulty at most the current worker's strength, which is exactly what that worker can earn. Sorting the workers makes the set of reachable jobs grow monotonically, so the pointer never moves backwards and each job is admitted once.
Complexity
- Time —
O(n log n + m log m) - Space —
O(n)
Pitfalls
- A harder job is not necessarily better paid, so the maximum has to be carried forward rather than read off the last admitted job.
- Trying to assign each job to at most one worker is a different (matching) problem.
- The total reaches about
10^4 · 10^5 = 10^9, which still fitsint— but only just.
Reference solution
Python
from typing import List
def maxProfitAssignment(difficulty: List[int], profit: List[int], worker: List[int]) -> int:
jobs = sorted(zip(difficulty, profit))
total = 0
j = 0
best = 0
for cap in sorted(worker):
while j < len(jobs) and jobs[j][0] <= cap:
best = max(best, jobs[j][1])
j += 1
total += best
return totalJava
public static int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.length;
int[][] jobs = new int[n][2];
for (int i = 0; i < n; i++) {
jobs[i][0] = difficulty[i];
jobs[i][1] = profit[i];
}
Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
int[] w = worker.clone();
Arrays.sort(w);
int total = 0, j = 0, best = 0;
for (int cap : w) {
while (j < n && jobs[j][0] <= cap) {
best = Math.max(best, jobs[j][1]);
j++;
}
total += best;
}
return total;
}C++
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int n = (int) difficulty.size();
vector<pair<int, int>> jobs(n);
for (int i = 0; i < n; i++) jobs[i] = make_pair(difficulty[i], profit[i]);
sort(jobs.begin(), jobs.end());
vector<int> w = worker;
sort(w.begin(), w.end());
int total = 0, j = 0, best = 0;
for (int cap : w) {
while (j < n && jobs[j].first <= cap) {
best = max(best, jobs[j].second);
j++;
}
total += best;
}
return total;
}JavaScript
var maxProfitAssignment = function(difficulty, profit, worker) {
var jobs = [];
for (var i = 0; i < difficulty.length; i++) jobs.push([difficulty[i], profit[i]]);
jobs.sort(function(a, b) { return a[0] - b[0]; });
var w = worker.slice().sort(function(a, b) { return a - b; });
var total = 0, j = 0, best = 0;
for (var k = 0; k < w.length; k++) {
while (j < jobs.length && jobs[j][0] <= w[k]) {
if (jobs[j][1] > best) best = jobs[j][1];
j++;
}
total += best;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms