# 826. Most Profit Assigning Work

## 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 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.

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

## Solutions

• class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int n = difficulty.length;
List<int[]> job = new ArrayList<>();
for (int i = 0; i < n; ++i) {
}
job.sort(Comparator.comparing(a -> a[0]));
Arrays.sort(worker);
int res = 0;
int i = 0, t = 0;
for (int w : worker) {
while (i < n && job.get(i)[0] <= w) {
t = Math.max(t, job.get(i++)[1]);
}
res += t;
}
return res;
}
}

• class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int n = difficulty.size();
vector<pair<int, int>> job;
for (int i = 0; i < n; ++i) {
job.push_back({difficulty[i], profit[i]});
}
sort(job.begin(), job.end());
sort(worker.begin(), worker.end());
int i = 0, t = 0;
int res = 0;
for (auto w : worker) {
while (i < n && job[i].first <= w) {
t = max(t, job[i++].second);
}
res += t;
}
return res;
}
};

• class Solution:
def maxProfitAssignment(
self, difficulty: List[int], profit: List[int], worker: List[int]
) -> int:
n = len(difficulty)
job = [(difficulty[i], profit[i]) for i in range(n)]
job.sort(key=lambda x: x[0])
worker.sort()
i = t = res = 0
for w in worker:
while i < n and job[i][0] <= w:
t = max(t, job[i][1])
i += 1
res += t
return res


• func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
var job [][2]int
for i := range difficulty {
job = append(job, [2]int{difficulty[i], profit[i]})
}

sort.SliceStable(job, func(i, j int) bool { return job[i][0] <= job[j][0] })
sort.Ints(worker)
i, t, n, res := 0, 0, len(difficulty), 0
for _, w := range worker {
for i < n && job[i][0] <= w {
t = max(t, job[i][1])
i++
}
res += t
}
return res
}

• function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
const n = profit.length;
worker.sort((a, b) => a - b);
const jobs = Array.from({ length: n }, (_, i) => [difficulty[i], profit[i]]);
jobs.sort((a, b) => a[0] - b[0]);
let [ans, mx, i] = [0, 0, 0];
for (const w of worker) {
while (i < n && jobs[i][0] <= w) {
mx = Math.max(mx, jobs[i++][1]);
}
ans += mx;
}
return ans;
}