. Kerja Penyerahan Keuntungan Paling Banyak

826. Kerja Memberi Keuntungan Paling Banyak

Sederhana

Anda mempunyai n pekerjaan dan m pekerja. Anda diberi tiga tatasusunan: kesukaran, keuntungan dan pekerja di mana:

• kesukaran[i] dan untung[i] ialah kesukaran dan keuntungan daripada pekerjaan^ke, dan
• worker[j] ialah keupayaan j^th pekerja (iaitu, pekerja j^th hanya boleh menyiapkan kerja dengan kesukaran pada kebanyakan pekerja[j]).

Setiap pekerja boleh diberikan paling banyak satu kerja, tetapi satu kerja boleh disiapkan beberapa kali.

• Sebagai contoh, jika tiga pekerja mencuba pekerjaan yang sama yang membayar $1, maka jumlah keuntungan ialah $3. Jika pekerja tidak dapat menyelesaikan sebarang kerja, keuntungan mereka ialah $0.

Pulangan keuntungan maksimum yang boleh kami capai selepas menugaskan pekerja kepada pekerjaan.

Contoh 1:

• Input: kesukaran = [2,4,6,8,10], untung = [10,20,30,40,50], pekerja = [4,5,6,7]
• Output: 100
• Penjelasan: Pekerja diberikan pekerjaan yang sukar [4,4,6,6] dan mereka mendapat keuntungan sebanyak [20,20,30,30] secara berasingan.

Contoh 2:

• Input: kesukaran = [85,47,57], keuntungan = [24,66,99], pekerja = [40,25,25]
• Output: 0

Kekangan:

• n == kesukaran.panjang
• n == untung.panjang
• m == pekerja.panjang
• 1 <= n, m <= 10⁴
• 1 <= kesukaran[i], untung[i], pekerja[i] <= 10⁵

Penyelesaian:

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




Pautan Kenalan


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . Kerja Penyerahan Keuntungan Paling Banyak. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!