. Börsengang

502. Börsengang

Schwer

Angenommen, LeetCode startet bald seinen Börsengang. Um seine Aktien zu einem guten Preis an Risikokapital zu verkaufen, möchte LeetCode vor dem Börsengang an einigen Projekten arbeiten, um sein Kapital zu erhöhen. Da die Ressourcen begrenzt sind, können höchstens k verschiedene Projekte vor dem Börsengang abgeschlossen werden. Helfen Sie LeetCode dabei, den besten Weg zur Maximierung seines Gesamtkapitals zu finden, nachdem höchstens k verschiedene Projekte abgeschlossen wurden.

Sie erhalten n Projekte, bei denen das i^te Projekt einen reinen Gewinngewinn[i] hat und für dessen Start ein Mindestkapital[i] erforderlich ist.

Zunächst verfügen Sie über Kapital. Wenn Sie ein Projekt abschließen, erhalten Sie dessen reinen Gewinn und der Gewinn wird Ihrem Gesamtkapital hinzugefügt.

Wählen Sie eine Liste von höchstens k verschiedenen Projekten aus gegebenen Projekten aus, um Ihr endgültiges Kapital zu maximieren und das endgültig maximierte Kapital zurückzugeben.

Die Antwort passt garantiert in eine 32-Bit-Ganzzahl mit Vorzeichen.

Beispiel 1:

• Eingabe: k = 2, w = 0, Gewinne = [1,2,3], Kapital = [0,1,1]
• Ausgabe: 4
• Erklärung:Da Ihr Anfangskapital 0 ist, können Sie das Projekt nur mit dem Index 0 starten.

Nach Abschluss erhalten Sie einen Gewinn von 1 und Ihr Kapital beträgt 1.

Mit Kapital 1 können Sie entweder das Projekt mit dem Index 1 oder das Projekt mit dem Index 2 starten.

Da Sie maximal 2 Projekte auswählen können, müssen Sie das Projekt mit Index 2 abschließen, um das maximale Kapital zu erhalten.

Geben Sie daher das endgültige maximierte Kapital aus, das 0 + 1 + 3 = 4 beträgt.

Beispiel 2:

• Eingabe: k = 3, w = 0, Gewinne = [1,2,3], Kapital = [0,1,2]
• Ausgabe: 6

Einschränkungen:

• 1 <= k <= 10⁵
• 0 <= w <= 10⁹
• n == profits.length
• n == Hauptstadt.Länge
• 1 <= n <= 10⁵
• 0 <= Gewinne[i] <= 10⁴
• 0 <= Kapital[i] <= 10⁹

Lösung:

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




Kontaktlinks


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt von. Börsengang. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!