英文原文
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.
You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.
Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.
Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
Example 1:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 4 Explanation: Since your initial capital is 0, you can only start the project indexed 0. After finishing it you will obtain profit 1 and your capital becomes 1. With capital 1, you can either start the project indexed 1 or the project indexed 2. Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital. Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Example 2:
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] Output: 6
Constraints:
1 <= k <= 1050 <= w <= 109n == profits.lengthn == capital.length1 <= n <= 1050 <= profits[i] <= 1040 <= capital[i] <= 109
中文题目
假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
答案保证在 32 位有符号整数范围内。
示例 1：
输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] 输出：4 解释： 由于你的初始资本为 0，你仅可以从 0 号项目开始。 在完成后，你将获得 1 的利润，你的总资本将变为 1。 此时你可以选择开始 1 号或 2 号项目。 由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。 因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。
示例 2：
输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] 输出：6
提示：
1 <= k <= 1050 <= w <= 109n == profits.lengthn == capital.length1 <= n <= 1050 <= profits[i] <= 1040 <= capital[i] <= 109
通过代码
高赞题解
贪心 + 优先队列（堆）
由于每完成一个任务都会使得总资金 w 增加或不变。因此对于所选的第 $i$ 个任务而言，应该在所有「未被选择」且启动资金不超过 w 的所有任务里面选利润最大的。
可通过「归纳法」证明每次都在所有候选中选择利润最大的任务，可使得总资金最大。
对于第 $i$ 次选择而言（当前所有的资金为 $w$），如果选择的任务利润为 $cur$，而实际可选的最大任务利润为 $max$（ $cur <= max$ ）。
将「选择 $cur$」调整为「选择 $max$」，结果不会变差：
- 根据传递性，由 $cur <= max$ 可得 $w + cur <= w + max$，可推导出调整后的总资金不会变少；
- 利用推论 $1$，由于总资金相比调整前没有变少，因此后面可选择的任务集合也不会变少。这意味着 至少可以维持 第 $i$ 次选择之后的所有原有选择。
至此，我们证明了将每次的选择调整为选择最大利润的任务，结果不会变差。
当知道了「每次都应该在所有可选择的任务里选利润最大」的推论之后，再看看算法的具体流程。
由于每完成一个任务总资金都会 增大/不变，因此所能覆盖的任务集合数量也随之 增加/不变 。
因此算法核心为「每次决策前，将启动资金不超过当前总资金的任务加入集合，再在里面取利润最大的任务」。
「取最大」的过程可以使用优先队列（根据利润排序的大根堆），而「将启动资金不超过当前总资金的任务加入集合」的操作，可以利用总资金在整个处理过程递增，而先对所有任务进行预处理排序来实现。
具体的，我们可以按照如下流程求解：
根据
profits和capital预处理出总的任务集合二元组，并根据「启动资金」进行升序排序；每次决策前，将所有的启动资金不超过 $w$ 的任务加入优先队列（根据利润排序的大根堆），然后从优先队列（根据利润排序的大根堆），将利润累加到 $w$；
循环步骤 $2$，直到达到 $k$ 个任务，或者队列为空（当前资金不足以选任何任务）。
代码：
[]class Solution { public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { int n = profits.length; List<int[]> list = new ArrayList<>(); for (int i = 0; i < n; i++) { list.add(new int[]{capital[i], profits[i]}); } Collections.sort(list, (a,b)->a[0]-b[0]); PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->b-a); int i = 0; while (k-- > 0) { while (i < n && list.get(i)[0] <= w) q.add(list.get(i++)[1]); if (q.isEmpty()) break; w += q.poll(); } return w; } }
- 时间复杂度：构造出二元组数组并排序的复杂度为 $O(n\log{n})$；大根堆最多有 $n$ 个元素，使用大根堆计算答案的复杂度为 $O(k\log{n})$。整体复杂度为 $O(\max(n\log{n}, k\log{n}))$
- 空间复杂度：$O(n)$
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 29785 | 67535 | 44.1% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
