Capital Project Picks

Problem

You start with some capital and may run at most rounds projects, one after another. Each project is a pair (cost, profit): you can only start it if your current capital is at least its cost, and finishing it adds its profit to your capital. Costs are never spent — they are only the bar you must clear. Return the capital you end with when you choose greedily for the largest final amount.

Examples

Input:  projects = [(0, 1), (1, 2), (2, 3)], capital = 0, rounds = 2
Output: 3
Why:    only (0, 1) is affordable, giving 1; then (1, 2) is, giving 3

Input:  projects = [(1, 3), (1, 4), (2, 9)], capital = 1, rounds = 2
Output: 14
Why:    take the profit of 4 first, which unlocks the project paying 9

Input:  projects = [(2, 5)], capital = 1, rounds = 1
Output: 1
Why:    edge case, nothing is affordable and the answer is the starting capital

Hints

0 / 3

1. Hint 1reveal
2. Hint 2locked
3. Hint 3locked

import heapq

def max_capital(projects, capital, rounds):
    locked = [(cost, profit) for cost, profit in projects]
    heapq.heapify(locked)                          # min-heap on cost
    ready, money = [], capital                     # max-heap on profit
    for _ in range(rounds):
        while locked and locked[0][0] <= money:    # newly affordable
            cost, profit = heapq.heappop(locked)
            heapq.heappush(ready, -profit)
        if not ready:                              # nothing can be started
            break
        money -= heapq.heappop(ready)              # a negated pop adds
    return money

print(max_capital([(0, 1), (1, 2), (2, 3)], 0, 2))   # -> 3
print(max_capital([(1, 3), (1, 4), (2, 9)], 1, 2))   # -> 14
print(max_capital([(2, 5)], 1, 1))                   # -> 1