IPO

Hard#502best of the affordable

You start with capital w and may finish at most k projects, one after another. Project n needs capital[n] to start, and once finished it adds profits[n] to the capital; nothing is spent. Return the largest capital you can end with. Our example: k = 3, w = 1, profits [4, 2, 5, 1, 3, 1], capital [3, 0, 6, 1, 2, 4] — the answer is 12: the projects with profits 2, 4 and 5, in that order.

502 IPOWalkthrough · 1×

Example: k = 3, w = 1, profits [4, 2, 5, 1, 3, 1], capital [3, 0, 6, 1, 2, 4]. On top the projects sorted by the capital they need; below, the max-heap of the profits we can afford.

capitalprofit012346213415w = 1max-heapof profits
locked: needs more than wjust pushed or takenin the heap, can be startedroot: the best profit we can afforddone, its profit added to w

Sort the projects by the capital they need: 0, 1, 2, 3, 4, 6

01/35
restart · back · play · step
Speed
1function findMaximizedCapital(k, w, profits, capital):
2 projects = pairs (capital, profit), sorted by capital
3 heap = empty max-heap // profits we can afford
4 i = 0
5 repeat k times:
6 while i < len(projects) and projects[i].capital <= w:
7 push projects[i].profit into heap
8 i = i + 1
9 if heap is empty:
10 return w
11 w = w + pop max from heap
12 return w
state
w
1
i
–
heap
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Capital only grows, so a project we can afford now stays affordable. Taking the largest profit first never closes a door: it only opens more projects for the next round.
  2. The projects are sorted by the capital they need, so i only moves forward: each round unlocks the next few, and every project enters the heap once.
  3. The heap keeps every unlocked project that is not taken yet, so its top is the best choice of the round, like the 5 taken last here.

Complexity

Time O(n log n + k log n): sorting n projects, then each enters and leaves the heap at most once. Memory O(n) for the sorted projects and the heap.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.