Re: [閒聊] 每日leetcode已回收
※ 引述《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
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 60.251.123.162 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718691073.A.E00.html
推
06/18 14:19,
1年前
, 1F
06/18 14:19, 1F
推
06/18 16:28,
1年前
, 2F
06/18 16:28, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 379 之 1549 篇)：