※ 引述《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
}
}