You are given an integer array workers, where workers[i] represents the skill level of the ith worker. You are also given a 2D integer array tasks, where:
tasks[i][0] represents the skill requirement needed to complete the task.
tasks[i][1] represents the profit earned from completing the task.
Each worker can complete at most one task, and they can only take a task if their skill level is equal to the task’s skill requirement. An additional worker joins today who can take up any task, regardless of the skill requirement.
Return the maximum total profit that can be earned by optimally assigning the tasks to the workers.
Input: workers =[10,10000,100000000], tasks =[[1,100]]Output: 100Explanation:
Since no worker matches the skill requirement, only the additional worker can complete task 0.
Input: workers =[7], tasks =[[3,3],[3,3]]Output: 3Explanation:
The additional worker completes task 1. Worker 0 cannot work since no task has a skill requirement of 7.
To maximize profit, assign the most profitable tasks to the most skilled workers. Sort both arrays and pair the largest profits with the largest skills.
classSolution {
public:int maxProfitAssignment(vector<int>& profit, vector<int>& worker) {
sort(profit.rbegin(), profit.rend());
sort(worker.rbegin(), worker.rend());
int n = min(profit.size(), worker.size()), ans =0;
for (int i =0; i < n; ++i) ans += profit[i] * worker[i];
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
classSolution {
publicintmaxProfitAssignment(int[] profit, int[] worker) {
Arrays.sort(profit);
Arrays.sort(worker);
int n = Math.min(profit.length, worker.length), ans = 0;
for (int i = 0; i < n; i++) {
ans += profit[profit.length-1-i]* worker[worker.length-1-i];
}
return ans;
}
}
1
2
3
4
5
6
7
8
classSolution:
defmaxProfitAssignment(self, profit: list[int], worker: list[int]) -> int:
profit.sort(reverse=True)
worker.sort(reverse=True)
ans =0for p, w in zip(profit, worker):
ans += p * w
return ans