Maximize Capital by Completing at Most k Projects
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A startup has an initial amount of capital `w` and is choosing which projects to take on before an important funding deadline. There are `n` candidate projects. Project `i` has:
- a capital requirement `capital[i]` — the startup must have **at least** this much capital on hand to start the project (the capital is a threshold, not a cost; it is not spent), and
- a pure profit `profit[i]` — completing the project adds this amount to the startup's capital.
The startup can complete **at most `k` distinct projects**, one at a time, in any order. After finishing a project, the profit is immediately added to its capital, which may unlock projects that were previously unaffordable. Each project can be completed at most once.
Return the **maximum possible final capital** after completing at most `k` projects.
**Example 1**
```
k = 2, w = 0
profit = [1, 2, 3]
capital = [0, 1, 1]
Output: 4
```
Explanation: with capital `0`, only project 0 (requirement 0) can be started; completing it raises capital to `1`. Now projects 1 and 2 are both unlocked; picking project 2 (profit 3) gives a final capital of `0 + 1 + 3 = 4`.
**Example 2**
```
k = 3, w = 0
profit = [1, 2, 3]
capital = [0, 1, 2]
Output: 6
```
Explanation: all three projects can be completed in order of increasing requirement, for a final capital of `1 + 2 + 3 = 6`.
**Constraints**
- $1 \le k \le 10^5$
- $1 \le n \le 10^5$
- $0 \le w \le 10^9$
- $0 \le profit[i] \le 10^4$
- $0 \le capital[i] \le 10^9$
- `profit.length == capital.length == n`
An efficient solution should run in $O\big((n + k)\log n\big)$ time; an $O(nk)$ brute force will be too slow at the largest inputs.
Quick Answer: This question evaluates algorithmic problem-solving and optimization skills within the Coding & Algorithms domain, focusing on selection under resource and operation constraints and reasoning about time and space complexity.
A startup has an initial amount of capital `w` and is choosing which projects to take on before an important funding deadline. There are `n` candidate projects. Project `i` has:
- a capital requirement `capital[i]` — the startup must have **at least** this much capital on hand to start the project (the capital is a threshold, not a cost; it is not spent), and
- a pure profit `profit[i]` — completing the project adds this amount to the startup's capital.
The startup can complete **at most `k` distinct projects**, one at a time, in any order. After finishing a project, the profit is immediately added to its capital, which may unlock projects that were previously unaffordable. Each project can be completed at most once.
Return the **maximum possible final capital** after completing at most `k` projects.
**Signature:** `solution(k, w, profits, capital)` returns an integer.
**Example 1**
```
k = 2, w = 0
profits = [1, 2, 3]
capital = [0, 1, 1]
Output: 4
```
With capital `0`, only project 0 (requirement 0) can be started; completing it raises capital to `1`. Now projects 1 and 2 are both unlocked; picking project 2 (profit 3) gives a final capital of `0 + 1 + 3 = 4`.
**Example 2**
```
k = 3, w = 0
profits = [1, 2, 3]
capital = [0, 1, 2]
Output: 6
```
All three projects can be completed in order of increasing requirement, for a final capital of `1 + 2 + 3 = 6`.
Constraints
- 1 <= k <= 10^5
- 1 <= n <= 10^5
- 0 <= w <= 10^9
- 0 <= profit[i] <= 10^4
- 0 <= capital[i] <= 10^9
- profit.length == capital.length == n
Examples
Input: (2, 0, [1, 2, 3], [0, 1, 1])
Expected Output: 4
Explanation: Start with 0; only project 0 (req 0) is affordable -> capital 1. Now projects 1 and 2 unlock; take project 2 (profit 3) -> 4.
Input: (3, 0, [1, 2, 3], [0, 1, 2])
Expected Output: 6
Explanation: Complete all three in order of increasing requirement: 0 -> 1 -> 3 -> 6.
Input: (1, 0, [5], [0])
Expected Output: 5
Explanation: Single project, affordable from the start, one pick allowed: 0 + 5 = 5.
Input: (3, 2, [1, 100], [5, 5])
Expected Output: 2
Explanation: Both projects need capital 5 but we only have 2 and nothing is affordable, so no project can be started; capital stays 2.
Input: (10, 0, [0, 0, 0], [0, 0, 0])
Expected Output: 0
Explanation: All projects affordable but every profit is 0, so capital never changes regardless of how many we complete.
Input: (2, 100, [10, 20, 30], [0, 0, 0])
Expected Output: 150
Explanation: All three are affordable immediately; with k=2 take the two largest profits (30 and 20): 100 + 30 + 20 = 150.
Input: (1, 1000000000, [10000], [0])
Expected Output: 1000010000
Explanation: Boundary values: one project of profit 10000 taken once on top of capital 1e9 -> 1000010000.
Hints
- Sort the projects by their capital requirement so you can efficiently sweep in all projects that become affordable as your capital grows.
- At each of the up to k steps you want the single most profitable project you can currently afford — a max-heap keyed on profit gives you that in O(log n).
- Each round: push every not-yet-added project whose requirement <= current capital into the max-heap, then pop the largest profit and add it to your capital. If the heap is empty, stop early — no further project can ever be unlocked.
- Capital never decreases (profit is added, not spent), so once a project is affordable it stays affordable; you never need to re-check earlier projects.