_502. IPO.md

502. IPO

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 15, 2024

Last updated : July 04, 2024

---

Related Topics : Array, Greedy, Sorting, Heap (Priority Queue)

Acceptance Rate : 53.08 %

---

    Notes
    k   --> max number of projects
    w   --> starting capital

    profits     --> profit from project i
    capital     --> investment needed for project i (NOT CONSUMED DURING MOVE)

---

Solutions

• h502 Daily.py

Python

h502 Daily.py

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        usableVals = []

        # zip of (profits, capital) sorted by capital
        # Profits are negative for later use since heapq is a minheap
        capitalAndProfits = sorted([(-1 * p, c) for p, c in zip(profits, capital)], 
                                    reverse=True, 
                                    key=lambda x : x[1])
        

        for i in range(k) :
            while capitalAndProfits and capitalAndProfits[-1][1] <= w :
                # Since profit is first, it will prioritize profits
                heapq.heappush(usableVals, capitalAndProfits.pop())

            if not usableVals :
                return w
            
            w -= heapq.heappop(usableVals)[0]   # subtract the negative profit

        return w