面试150 IPO

思路

首先，将每个项目的启动资本需求和对应的利润配对，组成一个二元组列表，并根据所需资本从小到大进行排序。这样可以确保在遍历项目列表时，能按所需资本的升序处理。接着，使用一个最大堆（通过在堆中存入利润的负值来实现）来维护当前资本下所有可选项目的利润。在每一轮（最多进行 k 轮）中，程序会将当前可承受的所有项目（即资本需求不超过当前拥有资本的项目）加入最大堆，然后从中选择利润最高的项目（堆顶元素），执行该项目并将其利润加到当前资本上。如果在某一轮没有任何可执行的项目，算法会提前退出。最终，返回选择最多 k 个项目后所能获得的最大资本。该算法通过贪心策略结合堆结构，兼顾了效率和最优选择。

import heapq
from typing import Listclass Solution:def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:num_projects = len(profits)project_list = []# 将每个项目的资本需求和对应利润配对for i in range(num_projects):project_list.append([capital[i], profits[i]])# 按所需资本升序排序project_list.sort()max_profit_heap = []  # 最大堆，用于存储可选项目的利润（取负值实现最大堆）project_index = 0available_capital = wfor _ in range(k):# 将当前资本可承受的项目加入最大堆while project_index < num_projects and project_list[project_index][0] <= available_capital:heapq.heappush(max_profit_heap, -project_list[project_index][1])project_index += 1if not max_profit_heap:break  # 没有可选项目，退出循环# 选择利润最高的项目max_profit = -heapq.heappop(max_profit_heap)available_capital += max_profitreturn available_capital