※ 引述《sustainer123 (caster )》之銘言：
: https://leetcode.com/problems/most-profit-assigning-work
: 826. Most Profit Assigning Work
: 你有n份工作與m個工人
: 給定三數列
: difficulty[i]與profit[i]代表第i份工作的收益與困難度
: worker[j]代表工人的能力
: 工人只能接受困難度小於等於自己能力的工作
: 每位工人只能接一份工作 但工作能被重複完成
: 請回傳我們將工作分配給工人後能獲得的最大收益
思路:
我用雙指標
先建立一組難度從小到大的Vec(難度,收益)
然後把工人能力從小排到大
接著開始看他們會甚麼
並且因為工人能力從小到大
所以i不用重置 下一個工人能力一定>=上一個
每次從上次看到的難度繼續就好
Code:
impl Solution {
pub fn max_profit_assignment(
difficulty: Vec<i32>,
profit: Vec<i32>,
mut worker: Vec<i32>,
) -> i32 {
let mut total_profit = 0;
let mut profit_by_difficulty: Vec<(i32, i32)> =
difficulty.into_iter().zip(profit.into_iter()).collect();
profit_by_difficulty.sort_unstable_by(|a, b| a.0.cmp(&b.0));
worker.sort();
let mut personal_max_profit = 0;
let mut i = 0;
for &ability in &worker {
while i < profit_by_difficulty.len() &&
ability >= profit_by_difficulty[i].0 {
personal_max_profit =
personal_max_profit.max(profit_by_difficulty[i].1);
i += 1;
}
total_profit += personal_max_profit;
}
total_profit
}
}