502.md

502 IPO

Description

link

---

Solution : HEAP

• 先将projects按照Capital情况做个排序
• 先循环找到第一个不满足当前W的project，其他全部入堆（通过负号实现最大堆，堆保存的是profit）
• 找到之后让堆pop出，则是满足当前条件的最大profit，加到W上，在K的范围内不断循环即可
• 使用堆的目的是减少求最大值的消耗

---

Code

Complexity T : O( klog(n) )

class Solution:
    def findMaximizedCapital(self, k: int, W: int, Profits: List[int], Capital: List[int]) -> int:
        heap = []
        projects = sorted(zip(Profits, Capital), key=lambda l: l[1])
        i = 0
        for _ in range(k):
            while i < len(projects) and projects[i][1] <= W:
                heapq.heappush(heap, -projects[i][0])
                i += 1
            if heap: W -= heapq.heappop(heap)
        return W