826. Most Profit Assigning Work
Medium
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 theith
job, and -
worker[j]
is the ability ofjth
worker (i.e., thejth
worker 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 aprofit 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
Solution:
class Solution {
/**
* @param Integer[] $difficulty
* @param Integer[] $profit
* @param Integer[] $worker
* @return Integer
*/
function maxProfitAssignment($difficulty, $profit, $worker) {
$ans = 0;
$jobs = array();
for ($i = 0; $i < count($difficulty); ++$i) {
$jobs[] = array($difficulty[$i], $profit[$i]);
}
sort($jobs);
sort($worker);
$i = 0;
$maxProfit = 0;
foreach ($worker as $w) {
for (; $i < count($jobs) && $w >= $jobs[$i][0]; ++$i) {
$maxProfit = max($maxProfit, $jobs[$i][1]);
}
$ans += $maxProfit;
}
return $ans;
}
}
Contact Links
Top comments (0)