565. Startup Capital
A small fund holds w units of money and can back at most k different ventures, one after another. Venture i needs capital[i] units on hand before it can be started (the money is not spent, only required to be available), and when it finishes it adds profits[i] units to the fund. Each venture can be backed at most once, and a finished venture's profit is available immediately for the next one.
Return the largest amount of money the fund can have after backing at most k ventures. It may back fewer than k if nothing affordable remains. The answer fits in a 32-bit signed integer.
Target O((n + k) log n) time and O(n) space.
Example 1
- Input:
- k = 2w = 1profits = [3,5,2]capital = [1,4,2]
- Output:
- 9
- Explanation:
Start with 1: only venture 0 is affordable (fund 4), then ventures 1 and 2 both are and the profit-5 one is best: 9.
Example 2
- Input:
- k = 3w = 0profits = [4,6]capital = [1,0]
- Output:
- 10
- Explanation:
Venture 1 first (fund 6), then venture 0 (fund 10); only two ventures exist, so the third slot goes unused.
Example 3
- Input:
- k = 1w = 2profits = [9,1]capital = [3,2]
- Output:
- 3
- Explanation:
Venture 0 needs 3 but only 2 is available, so the only choice is venture 1, giving 3.
Constraints
1 ≤ k ≤ 1000000 ≤ w ≤ 109n == profits.length == capital.length,1 ≤ n ≤ 1000000 ≤ profits[i] ≤ 1040 ≤ capital[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n + k log n)
- Space
- O(n)