Python C++ Sort,Priority Queue, Binary search解Leetcode難題502 IPO

Python C++ Sort Priority Queue Binary search解Leetcode難題502 IPO

建立一個容器 cp，裡面包含配對的資訊 (capital[i], profits[i])，其中 i 從 0 到 n-1。

將 cp 按照字典順序（預設排序）進行排序。

(Python code請進)

設置一個最大堆積（優先佇列）pq 來存放 profit[i] = cp[i][1]。

將 curr 設為 0，並使用一個從 i=0 到 k-1 的迴圈，執行以下操作：

在迴圈中，當 curr 小於n 且 cp[curr].first小於等於w 時，將 cp[curr].second 推入 pq。

如果 pq 不為空，則設置 w += pq.top()，並彈出該元素；否則，結束迴圈。

最終的 w 即為答案。

-----------------

Constuct a container cp with the info pair (capital[i], profits[i]) for i=0,...,n-1

Sort cp according to the lexicographic order( default ordering)

Set a max heap (priority_queue) pq to hold the profit[i]=cp[i][1]

Set curr=0 & use a loop for i=0 to k-1  do the following:

Use a loop while curr less than n and cp[curr].first less or = w push cp[curr].second to pq

If pq is not empty, set w += pq.top(), pop the element; otherwise break the loop

w is the answer

[codes on Leetcode]https://leetcode.com/problems/ipo/solutions/5315135/sort-priority-queue-binary-search-75ms-beats-99-60/

[Leetcode程式]https://www.youtube.com/watch?v=dybiq3pg-Os&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        n=len(profits)
        cp = list(zip(capital, profits))
        cp.sort()

        pq=[]
        curr=0
        for i in range(k):
            while curr<n and cp[curr][0]<=w:
                heapq.heappush(pq, -cp[curr][1])
                curr+=1
            if pq: w-=heapq.heappop(pq)
            else: break
        return w