LC 0502 [H] IPO - ALawliet/algorithms GitHub Wiki
use two heaps to find the max profit for the min capital
class Solution:
def findMaximizedCapital(self, k: int, W: int, Profits: List[int], Capital: List[int]) -> int:
numberOfProjects = k
initialCapital = W
minCapitalHeap = []
maxProfitHeap = []
for i in range(len(Profits)):
heappush(minCapitalHeap, (Capital[i], i))
availableCapital = initialCapital
for _ in range(numberOfProjects):
while minCapitalHeap and minCapitalHeap[0][0] <= availableCapital:
capital, i = heappop(minCapitalHeap)
heappush(maxProfitHeap, (-Profits[i], i))
if not maxProfitHeap:
break
availableCapital += -heappop(maxProfitHeap)[0]
return availableCapital