IPO
Hard · Heap & Counting · Array · Greedy · Sorting · Heap (Priority Queue)
Problem
A company preparing to go public wants to grow its capital by finishing projects. It starts with capital w and may finish at most k distinct projects, one at a time.
Project i can be started only while the company holds at least capital[i]. That amount is not spent: it is only a bar to clear. Finishing the project adds its pure profit profits[i] to the capital.
Choose the projects to maximize the final capital and return that final capital. The answer fits in a signed 32-bit integer.
Examples
Input: k = 2, w = 1, profits = [3,5,2], capital = [1,4,0] Output: 9
With 1 in hand, project 0 (+3) brings capital to 4, which unlocks project 1 (+5). Final capital: 9.
Input: k = 3, w = 0, profits = [1,2,3], capital = [1,1,2] Output: 0
Every project needs at least 1, so nothing can be started and capital stays 0.
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 6
Project 0 (+1) unlocks the others; then +3 and +2 give 6.
Constraints
- 1 <= k <= 10^5
- 0 <= w <= 10^9
- 1 <= n == len(profits) == len(capital) <= 10^5
- 0 <= profits[i] <= 10^4
- 0 <= capital[i] <= 10^9
Approaches
- Scan for the best affordable project at each step — time O(n · k), space O(n)
Follow-up
What if starting a project spent its capital requirement (you pay capital[i] and get back capital[i] + profits[i])? Net worth after a project is the same, but you may no longer afford the next one in the middle, so order matters differently. Here the bar is never spent, which is what makes "biggest affordable profit first" exact.
Related problems
Start free on Cariara · Coding problems · System design studio
