Re: [閒聊] 每日leetcode

[yam276 (虛構史學家)]

※ 引述《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
推 oin1104: 大師
推 SecondRun: 大師