389. IPO
A startup is preparing for its IPO and wants to enter it with as much capital as possible. You are given an integer k (the maximum number of projects it can complete), an integer w (its starting capital), and two equal-length arrays: profits[i] is the pure profit project i pays out when finished, and capital[i] is the minimum capital the company must already hold to start project i.
Projects are done one at a time. Starting project i requires current capital >= capital[i]; finishing it permanently adds profits[i] to the capital (starting a project costs nothing — capital[i] is a threshold, not a price). Each project can be done at most once.
Return the largest capital the company can hold after finishing at most k projects. The answer can exceed 32-bit range.
Example 1:
Input: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Output: 4
Explanation: With w = 0 only project 0 (threshold 0) is startable; finishing it raises capital to 1. Now projects 1 and 2 are both startable — taking the more profitable one (profit 3) ends at 1 + 3 = 4.
Example 2:
Input: k = 3, w = 0, profits = [1, 2, 3], capital = [0, 1, 2]
Output: 6
Explanation: Each finished project unlocks the next threshold: 0 → 1 → 3 → 6. All three projects fit within k = 3.
Constraints:
- 1 ≤ k ≤ 10⁵
- 0 ≤ w ≤ 10⁹
- 1 ≤ profits.length = capital.length ≤ 10⁵
- 0 ≤ profits[i] ≤ 10⁹
- 0 ≤ capital[i] ≤ 10⁹
- The answer fits in a signed 64-bit integer.
Hints:
Profits are never negative, so finishing a project can only grow your capital — and growing capital only unlocks more projects. That means there is never a reason to skip a round: greedily take the most profitable project you can currently afford.
"Most profitable affordable project" is a moving target as w grows. Sort projects by capital threshold once, keep a pointer that feeds every newly affordable profit into a max-heap, and pop the heap top k times. Each project enters and leaves the heap at most once.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Expected output: 4