05 August 2008
一个公司即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 公司 设计完成最多 k 个不同项目后得到最大总资本的方式。
给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
最初，资本为 w 。当你完成一个项目时，将获得纯利润，且利润将被添加到总资本中。
总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
答案保证在 32 位有符号整数范围内。
根据 profits 和 capital 预处理出总的任务集合二元组，并根据「启动资金」进行升序排序；
每次决策前，将所有的启动资金不超过 ww 的任务加入优先队列（根据利润排序的大根堆），然后从优先队列（根据利润排序的大根堆），将利润累加到 ww；
循环步骤 22，直到达到 kk 个任务，或者队列为空（当前资金不足以选任何任务）。
时间复杂度：构造出二元组数组并排序的复杂度为 O(nlogn)；大根堆最多有 n 个元素，使用大根堆计算答案的复杂度为 O(klogn)。整体复杂度为 O(max(nlogn,klogn))
空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int len = profits.length;
List<int[]> list = new ArrayList<>();
for (int i = 0; i < len; i++) {
list.add(new int[]{capital[i], profits[i]});
}
list.sort(Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
int i = 0;
while (k-- > 0) {
while (i < len && list.get(i)[0] <= w) q.add(list.get(i++)[1]);
if (q.isEmpty()) break;
w += q.poll();
}
return w;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
/*
贪心算法
https://leetcode.com/problems/ipo/discuss/98210/Very-Simple-(Greedy)-Java-Solution-using-two-PriorityQueues
*/
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<int[]> pqCap = new PriorityQueue<>((a,b) -> (a[0] - b[0]));
PriorityQueue<int[]> pqPro = new PriorityQueue<>((a,b) -> (b[1] - a[1]));
for (int i = 0; i < Profits.length; i++) {
pqCap.add(new int[] {Capital[i], Profits[i]});
}
for (int i = 0; i < k; i++) {
while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
pqPro.add(pqCap.poll());
}
if (pqPro.isEmpty()) {
break;
}
W += pqPro.poll()[1];
}
return W;
}
}