hypothesis Power button （LeetCode） begin in a minute IPO .
In order to sell shares to venture capital companies at a higher price , Power button Hope that in IPO Some projects have been carried out to increase its capital .
Due to limited resources , It can only be found in IPO Completed before most k individual Different projects .
help Power button Design completed at most k After two different projects, we get Maximum total capital The way .
Here you are. n A project . For each project i , It has a net profit
profits[i] , And start the project Minimum capital required
first , Yours Capital is w .
When you finish a project , You will get a net profit , And profits will be added to your total capital .
To make a long story short , Select... From a given project most k List of different items , With Maximize final capital , And export the most capital available .
The answer is guaranteed in 32 Bit signed integer range .
Example 1： Input ：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output ：4 explain ： Because your initial capital is 0, You can only from 0 Project start . After completion , You will receive 1 The profits of the , Your total capital will become 1. Now you can choose to start 1 Number or 2 Item No. . Because you can choose up to two items , So you need to finish 2 Project to maximize capital . therefore , Export the ultimate maximized capital , by 0 + 1 + 3 = 4. Example 2： Input ：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] Output ：6 Tips ： 1 <= k <= 10^5 0 <= w <= 10^9 n == profits.length n == capital.length 1 <= n <= 10^5 0 <= profits[i] <= 10^4 0 <= capital[i] <= 10^9
source ： Power button （LeetCode） link ：https://leetcode-cn.com/problems/ipo
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
- First, sort according to start-up funds
- Put the items you can get into the priority queue , Take out the most profitable
- Then check whether you can see more , repeat
class Solution: def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int: from queue import PriorityQueue q = PriorityQueue() item = list(zip(profits, capital)) # pack item.sort(key=lambda x : x) # Sort i, n = 0, len(item) while k: while i < n and w >= item[i]: # Can reach q.put(-item[i]) # python Priority queue small priority , Take a negative number i += 1 getMoney = False while not q.empty(): w += -q.get() # Got the proceeds getMoney = True break if not getMoney: break k -= 1 return w
796 ms 37.4 MB Python3
Long click or sweep code pay attention to my official account （Michael amin ）, Come on together 、 Learn together ！