Free Heaps lessonsHeaps · Stage 3 · Mastery · Step 2

Fund the best projects

Pick up to k projects one after another, each needing a minimum capital and returning a profit that adds to your capital, using a heap of the affordable projects ordered by profit. About 22 minutes.

Unlock, then choose

You have some capital w. Each project needs a certain capital to start and brings a profit that you keep. You may do at most k projects, one after another, and your capital grows with each profit.

At any moment, the projects you can afford are those needing at most w. Among these, the best choice is the most profitable one, since profit makes more projects affordable later and cannot hurt.

Affordable: capital needed at most what you have.

Choose: the most profitable one.

In code

ordered = sorted(items, key=lambda t: t[0])

k = 2, capital 1. Projects (capital needed, profit): (1, 2), (2, 5), (1, 3), (4, 8).

With capital 1, the projects needing 1 are affordable: profits 2 and 3. Take the more profitable, 3: capital becomes 4.

Move 1 of 3

A sorted list and a heap

Sort the projects by the capital they need. Keep an index into this list. Each round, move every project that is now affordable from the list into a max-heap keyed by profit.

Then take the top of the heap, add its profit to your capital, and repeat. If the heap is empty, nothing is affordable and you stop early, even if you did fewer than k projects. After at most k rounds, the capital is the answer.

Move to the heap: every newly affordable project.

Heap empty: stop; nothing more is possible.

In code

while i < n and cost[i] <= money:
    heapq.heappush(heap, -gain[i])
    i += 1

Quick check

Why take the most profitable affordable project, and not the cheapest one?

AMore capital makes more projects affordable later
BCheap projects are not allowed
CThe list is sorted by profit

Show the answer

More capital makes more projects affordable later. Profit is added to capital and only widens the choices.

Your problem

IPO

You may complete at most k projects and you start with capital w. Project i needs at least capital[i] to start and adds profits[i] to your capital when it is finished. Choose at most k different projects, one after another, and return the most capital you can end with.

Example

k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1] → 4

1 ≤ k ≤ 100,000 · 0 ≤ w ≤ 1,000,000,000 · 1 ≤ number of projects ≤ 3,000 · 0 ≤ profits[i] ≤ 10,000 · 0 ≤ capital[i] ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.