IPO
The key idea
At every step you may only start a project whose capital requirement you can already afford, and finishing it never lowers your capital (profits are non-negative). So the greedy choice is always the most profitable project among those currently affordable. A max-heap keyed on profit, fed by projects unlocked as capital rises (projects pre-sorted by capital), serves that best-affordable project in O(log n).
Problem
Suppose LeetCode will start its IPO soon. To raise money, it wants to pick a list of at most k distinct projects before the IPO. You are given n projects where the i-th project has a pure profit profits[i] and needs a minimum capital of capital[i] to start it.
Initially you have w capital. When you finish a project, you gain its pure profit, and that profit is added to your total capital. So your capital can only grow as you complete projects.
Pick from the projects a list of at most k distinct projects to maximize your final capital, and return the final maximized capital. The answer is guaranteed to fit in a 32-bit signed integer.
Constraints
1 <= k <= 10^50 <= w <= 10^9n == profits.lengthn == capital.length1 <= n <= 10^50 <= profits[i] <= 10^40 <= capital[i] <= 10^9
Examples
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6
Complexity
Time: O((n + k) log n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD
- Single-Threaded CPUMEDIUM