class Solution:
def maxProfitAssignment(self, difficulty, profit, worker):
jobs = sorted(zip(difficulty, profit))
worker.sort()
res = 0
best = 0
i = 0
n = len(jobs)
for ability in worker:
while i < n and jobs[i][0] <= ability:
best = max(best, jobs[i][1])
i += 1
res += best
return res
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
vector<pair<int,int>> jobs;
for (int i = 0; i < difficulty.size(); ++i)
jobs.push_back({difficulty[i], profit[i]});
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
int res = 0, best = 0, i = 0, n = jobs.size();
for (int ability : worker) {
while (i < n && jobs[i].first <= ability) {
best = max(best, jobs[i].second);
++i;
}
res += best;
}
return res;
}
};
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, best = 0, i = 0;
for (int ability : worker) {
while (i < n && jobs[i][0] <= ability) {
best = Math.max(best, jobs[i][1]);
++i;
}
res += best;
}
return res;
}
}
var maxProfitAssignment = function(difficulty, profit, worker) {
let jobs = [];
for (let i = 0; i < difficulty.length; ++i)
jobs.push([difficulty[i], profit[i]]);
jobs.sort((a, b) => a[0] - b[0]);
worker.sort((a, b) => a - b);
let res = 0, best = 0, i = 0, n = jobs.length;
for (let ability of worker) {
while (i < n && jobs[i][0] <= ability) {
best = Math.max(best, jobs[i][1]);
++i;
}
res += best;
}
return res;
};
difficulty
and profit
of the same length, where each difficulty[i]
is the difficulty of a job and profit[i]
is the profit for doing that job, and an array worker
representing the ability of each worker, assign jobs to workers to maximize total profit.
- Each worker can only do at most one job, and their ability must be at least the job's difficulty.
- Each job can be assigned to any number of workers (jobs are not "used up").
- Assign jobs so that each worker gets the job with the highest profit they can do.
- Return the maximum total profit that can be achieved by assigning jobs to all workers.
difficulty
and profit
into a list of jobs, then sort jobs by difficulty in ascending order.worker
array by ability in ascending order.difficulty = [2, 4, 6, 8, 10]
, profit = [10, 20, 30, 40, 50]
, and worker = [4, 5, 6, 7]
.
[(2,10), (4,20), (6,30), (8,40), (10,50)]
[4, 5, 6, 7]