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
Approach 01:
-
C++
-
Python
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
int total_profit = 0;
vector<pair<int, int>> jobs;
// Pair up difficulty and profit for each job
for (int i = 0; i < difficulty.size(); ++i)
jobs.emplace_back(difficulty[i], profit[i]);
// Sort jobs by difficulty and worker by their ability
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
int job_index = 0;
int max_profit_so_far = 0;
// Iterate over each worker's ability
for (const int ability : worker) {
// Find the maximum profit job the worker can do
while (job_index < jobs.size() &&
ability >= jobs[job_index].first) {
max_profit_so_far =
max(max_profit_so_far, jobs[job_index].second);
++job_index;
}
// Add the maximum profit the worker can achieve to the total profit
total_profit += max_profit_so_far;
}
return total_profit;
}
};
from typing import List
class Solution:
def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
total_profit = 0
jobs = []
# Pair up difficulty and profit for each job
for i in range(len(difficulty)):
jobs.append((difficulty[i], profit[i]))
# Sort jobs by difficulty and worker by their ability
jobs.sort()
worker.sort()
job_index = 0
max_profit_so_far = 0
# Iterate over each worker's ability
for ability in worker:
# Find the maximum profit job the worker can do
while job_index < len(jobs) and ability >= jobs[job_index][0]:
max_profit_so_far = max(max_profit_so_far, jobs[job_index][1])
job_index += 1
# Add the maximum profit the worker can achieve to the total profit
total_profit += max_profit_so_far
return total_profit