IPO
Problem statement
You start with capital w and may complete at most k projects, one after another. Project i can only be started if your current capital is at least capital[i], and finishing it adds profits[i] to your capital. Starting a project doesn't consume capital; it is only a threshold. Each project can be done at most once.
Choose the projects and their order to make your final capital as large as possible, and return it.
The catch is that finishing a project can unlock others you couldn't afford before.
Examples
Example 1
Input: k = 2, w = 1, profits = [3,1,4], capital = [1,0,5]
Output: 5
Explanation: With 1 you can do project 0 (+3) or project 1 (+1). Take project 0 to reach 4, then project 1 to reach 5. Project 2 needs 5 to start.
Example 2
Input: k = 3, w = 1, profits = [3,1,4], capital = [1,0,5]
Output: 9
Explanation: Same projects with a third turn: after reaching 5, project 2 is unlocked and adds 4.
Hints
Approach
Sort by threshold plus a max-heap of profits. Sort the projects by required capital. Keep a pointer into that sorted list and a max-heap of profits for projects you can afford.
Each round:
- Advance the pointer while the next project's capital is
<= w, pushing its profit onto the heap. Capital only grows, so a project, once affordable, stays affordable. - If the heap is empty, nothing is affordable: stop.
- Pop the largest profit and add it to
w.
Each project is pushed and popped at most once.
O(n log n + k log n)Space O(n)import heapq def find_maximized_capital(k, w, profits, capital): projects = sorted(zip(capital, profits)) heap, i = [], 0 # max-heap of affordable profits (negated) for _ in range(k): while i < len(projects) and projects[i][0] <= w: heapq.heappush(heap, -projects[i][1]) i += 1 if not heap: break w -= heapq.heappop(heap) return w print(find_maximized_capital(2, 1, [3, 1, 4], [1, 0, 5]))print(find_maximized_capital(3, 1, [3, 1, 4], [1, 0, 5]))Follow-up questions
- What if some projects have negative profit (a loss)? Does greedy still hold? (You would simply never pick them, since you may stop early.)
- Return which projects were chosen, in order.
Frequently asked questions
The shape is scheduling under a growing budget: work that can start only once enough capacity is available, where completing work frees or adds capacity. It is also a clean test of the two-structure pattern (a sorted list feeding a heap as a threshold rises), which reappears in job schedulers and task queues.
Profits are never negative and thresholds don't consume capital. Taking the most profitable affordable project leaves you with at least as much capital as any other choice, so every project another choice could unlock is also unlocked for you. An exchange argument makes this rigorous.
Capital decides when a project becomes available, and it only moves in one direction. Sorting by it lets a single pointer sweep forward, releasing projects into the heap exactly once. The heap then handles the profit ordering among what's available.