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
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving

Similar topics :LeetCode 1976. Number of options to reach the destination ( dijkstra Python Priority queue )

  • 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[1]) # Sort 
i, n = 0, len(item)
while k:
while i < n and w >= item[i][1]: # Can reach 
q.put(-item[i][0]) # 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


my CSDN Blog address https://michael.blog.csdn.net/

Long click or sweep code pay attention to my official account (Michael amin ), Come on together 、 Learn together !
Michael amin

Please bring the original link to reprint ,thank
Similar articles

2021-09-15

2021-09-15