Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
IPO
Bookmark
Input
Example 1
Example 2
Example 3
Custom
k
=
2
,
w
=
0
,
profits
=
[1, 2, 3]
,
capital
=
[0, 1, 1]
projects (capital, profit)
c=0
+1
c=1
+2
c=1
+3
fund the most profitable affordable project, k times
projects (capital, profit)
c=0
+1
c=1
+2
c=1
+3
fund the most profitable affordable project, k times
projects · sorted by capital
capital w =
0
max-heap
· profits
round
-
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
sort by capital → start with
w = 0
, pick
k = 2
projects · sorted by capital
capital w =
0
max-heap
· profits
round
1
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
capital
0
≤ w 0 → push profit
+1
projects · sorted by capital
capital w =
1
max-heap
· profits
round
1
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
fund best → w =
0
+
1
=
1
projects · sorted by capital
capital w =
1
max-heap
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
capital
1
≤ w 1 → push profit
+2
projects · sorted by capital
capital w =
1
max-heap
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
capital
1
≤ w 1 → push profit
+3
projects · sorted by capital
capital w =
4
max-heap
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
fund best → w =
1
+
3
=
4
projects · sorted by capital
capital w =
4
max-heap
· profits
round
2
/2
funded:
c=0
+1
c=1
+2
c=1
+3
final capital = 4 (2 projects funded)
algo
master
.
io
Step:
Start: pick up to 2 projects, always take the biggest affordable profit
0 / 7
Input
Example 1
Example 2
Example 3
Custom
k
=
2
,
w
=
0
,
profits
=
[1, 2, 3]
,
capital
=
[0, 1, 1]
0 / 7
algo
master
.
io
Step:
Start: pick up to 2 projects, always take the biggest affordable profit
