Seed Capital Projects
Problem
A small studio starts with capital w and may complete at most k distinct projects, one after another. Project i can only be started if the current capital is at least costs[i]; the cost is a requirement, not a payment, so it is not deducted. Finishing project i adds its pure profit profits[i] to the capital.
Choose the projects to maximise the final capital, and return that maximum.
Example 1
- Input:
- k = 2, w = 0, profits = [1, 2, 3], costs = [0, 1, 1]
- Output:
- 4
Only project 0 is affordable at first → capital 1. Now projects 1 and 2 are affordable; take project 2 (profit 3) → capital 4.
Example 2
- Input:
- k = 3, w = 1, profits = [5, 1, 4], costs = [3, 0, 2]
- Output:
- 11
Project 1 → 2, project 2 → 6, project 0 → 11.
Example 3
- Input:
- k = 1, w = 0, profits = [9], costs = [1]
- Output:
- 0
Nothing is affordable, so the capital stays 0.
Constraints
- 1 ≤ k ≤ 10^5
- 0 ≤ w ≤ 10^9
- 1 ≤ profits.length == costs.length ≤ 10^5
- 0 ≤ profits[i] ≤ 10^4, 0 ≤ costs[i] ≤ 10^9
Hint
Show the first hint
Capital never decreases. So once a project becomes affordable, it stays affordable.
Walkthrough
How to approach it
01Clarify before coding
- Is the cost paid? No, it is only a threshold; capital only grows by profits.
- Can a project be done twice? No, each at most once.
- Must we do exactly k? At most k; stop early if nothing is affordable.
02Brute force
Try every sequence of up to k affordable projects with backtracking and keep the best final capital.
Cost: O(n^k) sequences in the worst case; impossible for n = 10^5. Even the greedy with a linear scan per pick is O(k · n) = 10^10.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.