Choose Projects to Grow Capital
A start-up has capital capital and may complete at most k projects, one after another. Project i can only be started when the current capital is at least needed[i]; finishing it adds profit[i] to the capital (the needed amount is not spent). Each project can be done at most once.
Return the largest capital achievable. Write your own heap: repeatedly unlock every affordable project and take the most profitable one.
Example 1
Input: k = 3, capital = 1, profit = [2,5,3,1], needed = [1,4,2,0] Output: 11 Explanation: Take profits 2, 3 and 5 in that order: 1 → 3 → 6 → 11.
Example 2
Input: k = 1, capital = 0, profit = [5], needed = [1] Output: 0 Explanation: The only project needs capital 1.
Constraints
- 0 <= k <= 2 * 10^4
- 0 <= capital <= 10^9
- 1 <= profit.length == needed.length <= 2 * 10^4
- 0 <= profit[i] <= 10^4
- 0 <= needed[i] <= 10^9
Hint 1
Sort projects by the capital they need.
Hint 2
Push the profit of every newly affordable project into a max-heap, then take the top; repeat k times or until nothing is affordable.
Discussion 0
Join free to post in the discussion.
Good practice for: Backend Developer, Data Scientist, Blockchain Developer, Data Engineer, Full Stack Developer
Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.