. Introduction en bourse

502. Introduction en bourse

Dur

Supposons que LeetCode commence bientôt son IPO. Afin de vendre à bon prix ses actions à Venture Capital, LeetCode souhaiterait travailler sur quelques projets d'augmentation de capital avant l'IPO. Comme ses ressources sont limitées, elle ne peut terminer qu'un maximum de k projets distincts avant l'IPO. Aidez LeetCode à concevoir la meilleure façon de maximiser son capital total après avoir terminé au plus k projets distincts.

Vous recevez n projets où le i^ème projet a un pur profit[i] et un capital minimum de capital[i] est nécessaire pour le démarrer.

Au départ, vous avez w capital. Lorsque vous terminerez un projet, vous obtiendrez son profit pur et le profit sera ajouté à votre capital total.

Choisissez une liste de au plus k projets distincts à partir de projets donnés pour maximiser votre capital final, et restituez le capital final maximisé.

Il est garanti que la réponse tient dans un entier signé de 32 bits.

Exemple 1 :

• Entrée : k = 2, w = 0, bénéfices = [1,2,3], capital = [0,1,1]
• Sortie : 4
• Explication : Puisque votre capital initial est de 0, vous ne pouvez démarrer le projet qu'indexé 0.

Après l'avoir terminé, vous obtiendrez un bénéfice de 1 et votre capital deviendra 1.

Avec le majuscule 1, vous pouvez soit démarrer le projet indexé 1, soit le projet indexé 2.

Puisque vous pouvez choisir au maximum 2 projets, vous devez terminer le projet indexé 2 pour obtenir le capital maximum.

Par conséquent, extrayez le capital final maximisé, qui est 0 + 1 + 3 = 4.

Exemple 2 :

• Entrée : k = 3, w = 0, bénéfices = [1,2,3], capital = [0,1,2]
• Sortie : 6

Contraintes :

• 1 <= k <= 10⁵
• 0 <= w <= 10⁹
• n == profits.longueur
• n == capital.length
• 1 <= n <= 10⁵
• 0 <= bénéfices[i] <= 10⁴
• 0 <= majuscule[i] <= 10⁹

Solution :

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




Liens de contact


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!