IPO
Hard Sort by capital + max-heap of profits
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
You start with capital w and can finish at most k projects. Each project needs some minimum capital to start and adds its profit to your capital when done. Maximise final capital.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: with limited capital, finish up to k projects to maximise money.
Why this works: among projects you can afford right now, always take the most profitable. As money grows, more projects become affordable.
Example: k = 2, w = 0, profits [1, 2, 3], capital [0, 1, 1]
afford project 0 → w = 1now afford 1, 2 → take 3 → w = 4
✦Hints open one at a time
↗Approach
Sort by capital. Repeat k times: push all projects with capital <= w into the max-heap; if it's empty, stop; else add the top profit to w.
</>Solution (Java)
import java.util.*;
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(capital[a], capital[b]));
PriorityQueue<Integer> best = new PriorityQueue<>(Collections.reverseOrder());
int i = 0;
while (k-- > 0) {
while (i < n && capital[order[i]] <= w) best.offer(profits[order[i++]]); // newly affordable
if (best.isEmpty()) break;
w += best.poll();
}
return w;
}
}!Common mistake
Re-scanning all projects every round — O(n·k).
- Time: O(n log n + k log n).
- Space: O(n).