DSA problem
IPO
Suppose LeetCode will start its IPO soon. To sell shares at a good price, the company wants to maximize its capital by completing at most k distinct projects before the IPO. You are given n projects, where the i-th project has a pure profit of profits[i] and requires a minimum capital of capital[i] to start. Initially you have w capital. When you finish a project, the gained profit is added to your total capital. Pick at most k projects to maximize your final capital, and return that maximum.
A brute-force search would try every subset of size up to k, costing exponential time. A simpler greedy idea is, at each step, to scan all unfinished projects, filter those whose capital requirement is at most the current w, pick the one with the highest profit, and add its profit to w. That is correct but O(k * n) and too slow for large inputs.
The optimal approach combines sorting with two heaps. First sort the projects by their capital requirement in ascending order so that we can sweep through them in increasing order of cost. Maintain a max-heap keyed by profit to hold every project we can currently afford.
In each of the k rounds, push every project whose capital requirement is at most the current w onto the max-heap (using a moving index so each project is pushed at most once). If the heap is empty, no affordable project exists and we stop. Otherwise pop the project with the highest profit, add its profit to w, and continue. Each project is pushed and popped at most once, giving an overall time of O(n log n + k log n).
Examples
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]4k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]6k = 1, w = 2, profits = [1,2,3], capital = [1,1,2]5Constraints
- 1 <= k <= 10^5
- 0 <= w <= 10^9
- n == profits.length == capital.length
- 1 <= n <= 10^5
- 0 <= profits[i], capital[i] <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.