. IPO

502. IPO

Sukar

Andaikan LeetCode akan memulakan IPOnya tidak lama lagi. Untuk menjual harga sahamnya yang baik kepada Modal Teroka, LeetCode ingin mengusahakan beberapa projek untuk meningkatkan modalnya sebelum IPO. Memandangkan ia mempunyai sumber yang terhad, ia hanya boleh menyelesaikan paling banyak k projek berbeza sebelum IPO. Bantu LeetCode mereka bentuk cara terbaik untuk memaksimumkan jumlah modalnya selepas menyelesaikan paling banyak projek yang berbeza.

Anda diberi n projek di mana projek i^th mempunyai keuntungan keuntungan tulen[i] dan modal minimum[i] diperlukan untuk memulakannya.

Pada mulanya, anda ada w modal. Apabila anda menyelesaikan projek, anda akan memperoleh keuntungan tulennya dan keuntungan akan ditambah kepada jumlah modal anda.

Pilih senarai paling banyak k projek berbeza daripada projek yang diberikan untuk maksimumkan modal akhir anda dan pulangkan modal maksimum maksimum terakhir.

Jawapannya dijamin muat dalam integer bertanda 32-bit.

Contoh 1:

• Input: k = 2, w = 0, keuntungan = [1,2,3], modal = [0,1,1]
• Output: 4
• Penjelasan: Memandangkan modal permulaan anda ialah 0, anda hanya boleh memulakan projek yang diindeks 0.

Selepas selesai anda akan memperoleh keuntungan 1 dan modal anda menjadi 1.

Dengan modal 1, anda boleh sama ada memulakan projek yang diindeks 1 atau projek yang diindeks 2.

Memandangkan anda boleh memilih paling banyak 2 projek, anda perlu menyelesaikan projek yang diindeks 2 untuk mendapatkan modal maksimum.

Oleh itu, keluarkan modal maksimum akhir, iaitu 0 + 1 + 3 = 4.

Contoh 2:

• Input: k = 3, w = 0, keuntungan = [1,2,3], modal = [0,1,2]
• Output: 6

Kekangan:

• 1 <= k <= 10⁵
• 0 <= w <= 10⁹
• n == keuntungan.panjang
• n == modal.panjang
• 1 <= n <= 10⁵
• 0 <= keuntungan[i] <= 10⁴
• 0 <= modal[i] <= 10⁹

Penyelesaian:

class Solution {

    /**
     * @param Integer $k
     * @param Integer $w
     * @param Integer[] $profits
     * @param Integer[] $capital
     * @return Integer
     */
    function findMaximizedCapital($k, $w, $profits, $capital) {
        $n = count($capital);
        $minCapitalHeap = new SplMinHeap();
        for ($i = 0; $i < $n; ++$i) {
            $minCapitalHeap->insert([$capital[$i], $profits[$i]]);
        }
        $maxProfitHeap = new SplMaxHeap();
        while ($k-- > 0) {
            while (!$minCapitalHeap->isEmpty() && $minCapitalHeap->top()[0] <= $w) {
                $maxProfitHeap->insert($minCapitalHeap->extract()[1]);
            }
            if ($maxProfitHeap->isEmpty()) {
                break;
            }
             $w += $maxProfitHeap->extract();
        }
        return $w;
    }
}




Pautan Kenalan


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci . IPO. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!