IPO
Problem Statement
You are given k, initial capital w, and two arrays profits and capital. Project i requires at least capital[i] current capital before it can be started and then adds profits[i] to your capital when completed. Choose at most k distinct projects to maximize final capital.
Input
Integers k and w, plus equal-length arrays profits and capital describing project rewards and minimum capital requirements.
Output
An integer: the maximum capital reachable after choosing at most k projects.
Constraints
- •
1 <= k <= 10^5 - •
0 <= w <= 10^9 - •
1 <= profits.length <= 10^5 - •
profits.length == capital.length - •
0 <= profits[i] <= 10^4 - •
0 <= capital[i] <= 10^9
Examples
Example 1
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
4Example 2
k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
6Example 3
k = 1, w = 2, profits = [1,2,3], capital = [1,1,2]
5Learning Objectives
- Separate projects that are affordable now from projects that may become affordable later.
- Use a max-heap to choose the best profit among currently affordable projects.
- Use a min-heap by capital requirement to feed the affordable set efficiently.
- Prove why taking the highest available profit can only unlock at least as many future options as any smaller profit.
Intuition
The greedy insight is that at any moment, projects split into two groups: affordable and locked. You cannot choose from the locked group yet, so the only meaningful decision is which affordable project to do next.
Among affordable projects, choosing the largest profit is always safe. It gives the maximum possible capital after this step, and having more capital never removes future projects. Two heaps make this online: a min-heap by capital reveals newly affordable projects, and a max-heap by profit selects the best affordable project.
This is a heap-driven greedy expansion. Unlike Course Schedule III or Furthest Building, the heap is not undoing a previous choice; it is upgrading the current choice as the feasible set grows.
Common mistakes
- ×Sorting by profit once and scanning from the top, which repeatedly skips locked projects inefficiently.
- ×Taking the cheapest capital requirement instead of the highest profit among affordable projects.
- ×Forgetting to stop early when no project is affordable, even if fewer than **k** projects have been selected.
- ×Pushing all projects into the profit heap before checking whether their capital requirements are affordable.
Algorithm Explanation
Greedy strategy
Always choose the highest-profit project among projects whose capital requirement is at most current capital. Keep locked projects in a min-heap by capital requirement, and move every newly affordable project into a max-heap of profits before each choice.
Why it works
At a selection step, locked projects are impossible to choose. Among affordable projects, a higher profit produces capital that is at least as large as choosing any lower profit. More capital can only unlock more projects; it never makes an affordable project unavailable.
Proof of correctness
Take any optimal sequence of remaining projects at some step, and suppose it chooses an affordable project with profit p while another affordable project has profit q >= p. Swap the first choice to the project with profit q. After this swapped choice, capital is at least as large as in the original sequence, so every project that was affordable later in the original sequence is still affordable at the same or earlier time. The swapped sequence can complete at least the same number of projects and end with at least as much capital. Repeating this exchange makes an optimal sequence choose the maximum affordable profit at every step, exactly what the heap algorithm does.
Algorithm
- Push every project as [capital, profit] into a min-heap ordered by capital.
- Keep a max-heap of profits for projects affordable now.
- Repeat up to k times.
- Move every project whose required capital is at most current capital from the capital heap to the profit heap.
- If the profit heap is empty, break because no further project can be started.
- Poll the largest profit and add it to current capital.
- Return current capital.
Solutions
Solution: Two heaps: capital gate and max-profit choice
Use one min-heap to hold locked projects ordered by required capital and one max-heap to hold profits of projects that are affordable right now. Each selection first drains the capital heap into the profit heap as far as current capital allows, then takes the maximum affordable profit.
Step-by-step
- Push each project into lockedProjects as [capital[i], profits[i]], ordered by required capital.
- Initialise currentCapital = w and an empty max-heap affordableProfits.
- Before each selection, move all projects whose capital requirement is at most currentCapital into affordableProfits.
- If affordableProfits is empty, stop early because no project can currently be started.
- Poll the largest profit and add it to currentCapital.
- After at most k selections, return currentCapital.
O((n + k) log n)
O(n)
Each project is inserted into the capital heap, moved once to the profit heap, and at most k profits are selected.
Java implementation
Dry Run
Sample input
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]. The capital min-heap starts with [0,1], [1,2], [1,3].
| selection | capital before | capital heap before unlock | moved to profit heap | profit max-heap | capital after |
|---|---|---|---|---|---|
| 1 | 0 | [[0,1],[1,2],[1,3]] | [1] | [1] | 1 |
| 2 | 1 | [[1,2],[1,3]] | [2,3] | [3,2] | 4 |
Starting with capital 0, only the profit 1 project is affordable. After taking it, capital becomes 1, which unlocks the two remaining projects. The max-heap chooses profit 3, giving final capital 4.
Interview Tips
Make the feasibility boundary explicit. The capital min-heap is not choosing projects; it only discovers what has become affordable. The actual greedy choice is from the max-profit heap. This distinction prevents the common mistake of choosing the lowest-capital project when a higher-profit affordable project is available.
Likely follow-ups
- What if project profits could be negative and you may choose fewer than **k** projects?
- How would you return the selected project indices in order?
- What if each project had a duration and only projects completed before a deadline counted?
- How would the algorithm change if capital was consumed when starting a project instead of only required as a threshold?
Similar Problems
Key Takeaways
- Locked choices are irrelevant until capital makes them affordable.
- Among affordable projects, maximum profit is a safe greedy choice because more capital never hurts.
- A min-heap by capital plus a max-heap by profit separates discovery from selection.
- Stop early when the affordable heap is empty; choosing more projects is impossible.