。 IPO

502. IPO

ハード

LeetCode がすぐに IPO を開始するとします。自社の株式をベンチャーキャピタルに良い価格で売却するために、LeetCode はIPO前に資本を増やすいくつかのプロジェクトに取り組みたいと考えています。リソースが限られているため、IPO までに完了できるプロジェクトは最大でも k 個までです。 LeetCode が、k 個以上の異なるプロジェクトを完了した後に総資本を最大化するための最良の方法を設計するのを支援してください。

n 個のプロジェクトが与えられ、i ^番目 プロジェクトには純粋な利益 Profit[i] があり、それを開始するには資本[i] の最小資本が必要です。

最初、あなたは w 資本を持っています。プロジェクトが完了すると、純粋な利益が得られ、その利益が総資本に追加されます。

指定されたプロジェクトから最大 k 個の異なるプロジェクトのリストを選択して、最終資本を最大化し、最終的に最大化された資本を返します。

答えは 32 ビットの符号付き整数に収まることが保証されています。

例 1:

• 入力: k = 2、w = 0、利益 = [1,2,3]、資本 = [0,1,1]
• 出力: 4
• 説明: 初期資本は 0 であるため、インデックス 0 のプロジェクトのみを開始できます。

完了すると利益 1 が得られ、資本が 1 になります。

大文字 1 を使用すると、インデックス 1 のプロジェクトを開始するか、インデックス 2 のプロジェクトを開始できます。

最大で 2 つのプロジェクトを選択できるため、最大の資金を獲得するには、インデックス 2 のプロジェクトを完了する必要があります。

したがって、最終的な最大化資本、0 + 1 + 3 = 4 を出力します。

例 2:

• 入力: k = 3、w = 0、利益 = [1,2,3]、資本 = [0,1,2]
• 出力: 6

制約:

• 1 5
• 0 9
• n == 利益.長さ
• n == Capital.length
• 1 5
• 0 4
• 0 9

解決策:

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

連絡先リンク

• LinkedIn
• GitHub

以上が。 IPOの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。