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]andprofit[i]are the difficulty and the profit of theithjob, andworker[j]is the ability ofjthworker (i.e., thejthworker can only complete a job with difficulty at mostworker[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.lengthn == profit.lengthm == worker.length1 <= n, m <= 1041 <= difficulty[i], profit[i], worker[i] <= 105
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int res = 0;
vector < vector<int>>v;
for(int i = 0; i < difficulty.size(); i++) v.push_back({difficulty[i], profit[i]});
sort(v.begin(), v.end(), [](vector<int>& v1, vector<int>& v2){ return v1[0] < v2[0]; });
int maxProfit = 0;
for(auto& x: v){
maxProfit = max(maxProfit, x[1]);
x[1] = maxProfit;
}
for(auto& x: worker){
int pos = upper_bound(v.begin(), v.end(), x, [](int v1, vector<int>& v2){ return v1 < v2[0]; }) - v.begin() - 1;
if(pos >= 0) res += v[pos][1];
}
return res;
}
};
Input
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output
100
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
List tasks = new ArrayList<>();
for (int i = 0; i < difficulty.length; i++) {
tasks.add(new Task(profit[i], difficulty[i]));
}
tasks.sort(Comparator.comparingInt(o -> o.difficulty));
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) {
workerProfit = Math.max(workerProfit, tasks.get(idx++).profit);
}
maxProfit += workerProfit;
}
return maxProfit;
}
class Task {
int profit;
int difficulty;
public Task(int profit, int difficulty) {
this.profit = profit;
this.difficulty = difficulty;
}
}
}
Input
difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output
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[0] - b[0])
worker.sort((a, b) => a - b)
let i = 0, tmp = 0
for(let w of worker) {
while(i < n && w >= jobs[i][0]) {
tmp = Math.max(tmp, jobs[i++][1])
}
res += tmp
}
return res
};
Input
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][0]:
maxp = max(jobs[i][1], maxp)
i += 1
res += maxp
return res
Input
difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]