## Algorithm

Problem Name: 826. Most Profit Assigning Work

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`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int maxProfitAssignment(vector& difficulty, vector& profit, vector& worker) {
int res = 0;
vector>v;
for(int i = 0; i < difficulty.size(); i++) v.push_back({difficulty[i], profit[i]});
sort(v.begin(), v.end(), [](vector& v1, vector& v2){ return v1 < v2; });
int maxProfit = 0;
for(auto& x: v){
maxProfit = max(maxProfit, x);
x = maxProfit;
}
for(auto& x: worker){
int pos = upper_bound(v.begin(), v.end(), x, [](int v1, vector& v2){ return v1 < v2; }) - v.begin() - 1;
if(pos >= 0) res += v[pos];
}
return res;
}
};
``````
Copy The Code &

Input

cmd
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]

Output

cmd
100

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
for (int i = 0; i < difficulty.length; i++) {
}
Arrays.sort(worker);
int idx = 0;
int maxProfit = 0;
int workerProfit = 0;
for (int ability : worker) {
while (idx < profit.length && ability >= tasks.get(idx).difficulty) {
}
maxProfit += workerProfit;
}
return maxProfit;
}

int profit;
int difficulty;

public Task(int profit, int difficulty) {
this.profit = profit;
this.difficulty = difficulty;
}
}
}
``````
Copy The Code &

Input

cmd
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]

Output

cmd
100

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxProfitAssignment = function(difficulty, profit, worker) {
let res = 0
const n = profit.length
const jobs = []
for(let i = 0; i < n; i++) {
jobs.push([difficulty[i], profit[i]])
}
jobs.sort((a,b) => a - b)
worker.sort((a, b) => a - b)
let i = 0, tmp = 0
for(let w of worker) {
while(i < n && w >= jobs[i]) {
tmp = Math.max(tmp, jobs[i++])
}
res += tmp
}

return res
};
``````
Copy The Code &

Input

cmd
difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxProfitAssignment(self, difficulty, profit, worker):
"""
:type difficulty: List[int]
:type profit: List[int]
:type worker: List[int]
:rtype: int
"""
jobs = sorted([a, b] for a, b in zip(difficulty, profit))
res = i = maxp = 0
for ability in sorted(worker):
while i < len(jobs) and ability >= jobs[i]:
maxp = max(jobs[i], maxp)
i += 1
res += maxp
return res
``````
Copy The Code &

Input

cmd
difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]