Posted on 2023-02-24 00:07
Uriel 阅读(37)
评论(0) 编辑 收藏 引用 所属分类:
贪心 、
闲来无事重切Leet Code
有n个projects，每个需要capacity[i]才能启动，获利profits[i]，初始拥有w capacity，问完成最多k个projects可以最多获利多少
利用heap（or优先队列）的贪心
先按照capacity从小到大对projects排序，然后从第一个project开始，如果capacity小于当前的w，则加入heap，直到capacity的要求大于当前w，然后去完成heap顶端的project
1 #502
2 #Runtime: 1335 ms (Beats 51.90%)
3 #Memory: 37.9 MB (Beats 69.62%)
4
5 class Solution(object):
6 def findMaximizedCapital(self, k, w, profits, capital):
7 """
8 :type k: int
9 :type w: int
10 :type profits: List[int]
11 :type capital: List[int]
12 :rtype: int
13 """
14 n = len(profits)
15 proj = list(zip(capital, profits))
16 proj.sort()
17 j = 0
18 q = []
19 for i in range(k):
20 while j < n and proj[j][0] <= w:
21 heappush(q, -proj[j][1])
22 j += 1
23 if not q:
24 break
25 w += -heappop(q)
26 return w