。最も利益を与える仕事-PHPチュートリアル-php.cn

。最も利益を与える仕事

王林

リリース： 2024-07-18 06:44:44

オリジナル

976 人が閲覧しました

. Most Profit Assigning Work

826。最も利益をもたらす仕事

中

あなたには n 個の仕事と m 個の労働者がいます。難易度、利益、労働者の 3 つの配列が与えられます。

難易度[i] と利益[i] は、i^番目ジョブの難易度と利益、
worker[j] は、j^th Worker の能力です (つまり、j^th Worker は、worker[j] の難易度でのみジョブを完了できます)。

すべてのワーカーには最大 1 つのジョブを割り当てることができますが、1 つのジョブは複数回完了することができます。

たとえば、3 人の労働者が 1 ドルを支払う同じ仕事に挑戦した場合、合計の利益は 3 ドルになります。労働者が仕事を完了できなかった場合、利益は 0 ドルになります。

労働者をジョブに割り当てた後に達成できる最大利益を返します。

例 1:

入力: 難易度 = [2,4,6,8,10]、利益 = [10,20,30,40,50]、労働者 = [4,5,6,7]
出力: 100
説明: 労働者には難易度 [4,4,6,6] の仕事が割り当てられ、個別に [20,20,30,30] の利益が得られます。

例 2:

入力: 難易度 = [85,47,57]、利益 = [24,66,99]、労働者 = [40,25,25]
出力: 0

制約:

n == 難易度.長さ
n == 利益.長さ
m == worker.length
1 4
1 5

解決策:

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;
    }
}

ログイン後にコピー

連絡先リンク