This solution uses a greedy algorithm combined with a priority queue (heap) to efficiently select projects that maximize capital. Initially, it checks if the starting capital 'w' is greater than or equal to the highest capital requirement among the projects. If this is the case, it sorts the profits in descending order and picks the top 'k' to get the maximum profit immediately. Otherwise, it pairs each project with its capital and profit, sorts these pairs based on capital, and then uses a max-heap to keep track of the most profitable projects that can be started with the current capital. In each iteration (up to 'k' times), it pushes all feasible projects (based on current capital) into the heap and then selects the project with the highest profit. The profit of the selected project is added to the capital, and this process repeats until 'k' projects are completed or no further projects can be initiated.
时间复杂度: O(n log n)
空间复杂度: O(n)
import heapq
class Solution:
def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
if w >= max(capital):
# If initial capital is greater than all project requirements, sort and pick the top k profitable projects
return w + sum(sorted(profits)[-k:])
n = len(profits)
current = 0
items = list(zip(capital, profits))
items.sort(key=lambda x: x[0]) # Sort projects by capital requirement
heap = []
for _ in range(k):
while current < n and items[current][0] <= w: # Push feasible projects to max-heap
heapq.heappush(heap, -items[current][1]) # Use negative to simulate a max-heap using min-heap
current += 1
if not heap:
break
w -= heapq.heappop(heap) # Pop the project with the max profit
return w