# Leetcode 502. IPO (priority queue)

Michael Amin 2021-09-15 08:45:10

## 1. subject

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 `capital[i]` .

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

## 2. Problem solving

• 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 ！ 