IPO
Understanding the Problem
We have a set of projects, each requiring some minimum capital to start and yielding a certain profit upon completion. We start with w capital and can complete at most k projects. After completing a project, its profit gets added to our capital, potentially unlocking more expensive projects. The goal is to maximize the final capital.
A greedy rule solves this: at each step, among all projects we can currently afford, pick the one with the highest profit. That gives us the most capital for future rounds, which in turn unlocks the most options. The challenge is doing this efficiently. With up to 10^5 projects and 10^5 rounds, we need a data structure that returns the most profitable affordable project quickly.
Key Constraints:
1 <= k <= 10^5and1 <= n <= 10^5→ We might iterate up to k times, and each iteration needs to efficiently find the best project. A naive O(n) scan per iteration gives O(k * n) = O(10^10), which is too slow.0 <= w <= 10^9and0 <= capital[i] <= 10^9→ Capital values can be very large, so we can't use them as array indices. No bucket sort tricks.0 <= profits[i] <= 10^4→ Profits are non-negative, so completing more projects never decreases our capital. This is why running for the full k rounds (when projects remain affordable) is safe.
Approach 1: Brute Force (Greedy with Linear Scan)
Intuition
The greedy rule says: always pick the most profitable project we can afford. A direct implementation scans all projects each round, finds the one with the highest profit among those whose capital requirement is at most our current capital, completes it, and repeats up to k times.
Each project can only be completed once, so we track which projects have been used with a boolean array.
Algorithm
- Create a boolean array
usedof size n, initialized to false. - Repeat up to k times:
- Scan all n projects. Among those not yet used and whose
capital[i] <= w, find the one with the maximumprofits[i]. - If no affordable project exists, stop early.
- Mark that project as used and add its profit to
w. - Return
w.
Example Walkthrough
Code
- Time Complexity: O(k n). Each of the k rounds scans all n projects. In the worst case this is O(10^5 10^5) = O(10^10), which is far too slow.
- Space Complexity: O(n). The boolean
usedarray takes O(n) space.
This approach is correct but too slow for large inputs, because it re-scans every project on every round. The next approach removes the repeated scanning by sorting projects by capital and using a max-heap to retrieve the best affordable project in logarithmic time.
Approach 2: Greedy with Sort + Max-Heap (Optimal)
Intuition
Once a project becomes affordable, it stays affordable, because our capital only increases. So instead of re-scanning every project each round, we sort projects by their capital requirement and use a pointer to track which ones we have unlocked so far.
The plan: sort all projects by capital. Maintain a max-heap of profits for all projects we can currently afford. Each round, push any newly affordable projects into the max-heap (the previous round increased our capital, so more may have become reachable), then pop the top to get the most profitable one. The pointer never moves backward because capital only grows.
Picking the most profitable affordable project first is safe because of an exchange argument. Suppose an optimal solution completes some other affordable project P first instead of the highest-profit affordable project H. Profits are non-negative, so swapping P for H in that first slot gives capital that is at least as high at every later step. The set of projects affordable after taking H is therefore a superset of those affordable after taking P, so any remaining choices the optimal solution made are still available. The swapped solution earns at least as much, so the greedy choice loses nothing.
The cost stays low because each project is pushed into and popped from the heap at most once, and the pointer only moves forward. Across all k rounds the total heap work is O(n log n).
Algorithm
- Pair each project as
(capital[i], profits[i])and sort by capital ascending. - Initialize a pointer
idx = 0and a max-heap (empty). - Repeat k times:
- While
idx < nandprojects[idx].capital <= w, pushprojects[idx].profitinto the max-heap and incrementidx. - If the max-heap is empty, no more affordable projects exist. Stop early.
- Pop the maximum profit from the heap and add it to
w. - Return
w.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). Each of the n projects is pushed into and popped from the heap at most once, each operation costing O(log n). The total heap work is O(n log n).
- Space Complexity: O(n). The sorted projects array and the heap each store up to n elements.