Most Profit Assigning Work
Problem
You have jobs with difficulties and profits, and workers with abilities. Each worker can do one job whose difficulty is <= their ability and earns its profit. Return the maximum total profit.
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]100def maxProfitAssignment(difficulty, profit, worker):
jobs = sorted(zip(difficulty, profit))
worker.sort()
res = i = best = 0
for w in worker:
while i < len(jobs) and jobs[i][0] <= w:
best = max(best, jobs[i][1])
i += 1
res += best
return res
function maxProfitAssignment(difficulty, profit, worker) {
const jobs = difficulty.map((d, i) => [d, profit[i]]).sort((a, b) => a[0] - b[0]);
worker.sort((a, b) => a - b);
let res = 0, i = 0, best = 0;
for (const w of worker) {
while (i < jobs.length && jobs[i][0] <= w) {
best = Math.max(best, jobs[i][1]);
i++;
}
res += best;
}
return res;
}
import java.util.*;
class Solution {
public 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) -> a[0] - b[0]);
Arrays.sort(worker);
int res = 0, i = 0, best = 0;
for (int w : worker) {
while (i < n && jobs[i][0] <= w) { best = Math.max(best, jobs[i][1]); i++; }
res += best;
}
return res;
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int n = difficulty.size();
vector<pair<int,int>> jobs(n);
for (int i = 0; i < n; i++) jobs[i] = {difficulty[i], profit[i]};
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
int res = 0, i = 0, best = 0;
for (int w : worker) {
while (i < n && jobs[i].first <= w) { best = max(best, jobs[i].second); i++; }
res += best;
}
return res;
}
};
Explanation
Each worker should take the most profitable job they can handle (any job whose difficulty is at most their ability). The clever part is doing this for all workers efficiently instead of re-searching the jobs for each one.
We first pair each job as (difficulty, profit) and sort jobs by difficulty. We also sort the workers by ability. Now both lists go from weakest to strongest.
We sweep through workers with a job pointer i that only moves forward. For each worker w, we advance i over every job they can now reach (jobs[i][0] <= w), keeping a running best = the highest profit unlocked so far. Because workers only get stronger, every job unlocked for an earlier worker is still available to later ones, so best never needs to reset.
Each worker then simply adds best to the total. A worker with no reachable job contributes 0.
Example: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]. The best reachable profits are 20, 20, 30, 30, summing to 100.