Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
IPO
Bookmark
Linear Scan
Sort + Max-Heap
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
sort by capital → start with
w = 0
, pick
k = 2
projects (capital, profit)
c=0
+1
c=1
+2
c=1
+3
fund the most profitable affordable project, k times
sort by capital → start with
w = 0
, pick
k = 2
projects · sorted by capital
capital w =
0
linear scan
· profits
round
1
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
check
project 0
, best so far
none
projects · sorted by capital
capital w =
0
linear scan
· profits
round
1
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
check
project 0
, best so far
project 0
projects · sorted by capital
capital w =
0
linear scan
· profits
round
1
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
check
project 2
, best so far
project 0
projects · sorted by capital
capital w =
1
linear scan
· 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
linear scan
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
projects · sorted by capital
capital w =
1
linear scan
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
check
project 1
, best so far
none
projects · sorted by capital
capital w =
1
linear scan
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
check
project 2
, best so far
project 1
projects · sorted by capital
capital w =
1
linear scan
· profits
round
2
/2
funded:
i
c=0
+1
c=1
+2
c=1
+3
check
project 2
, best so far
project 2
projects · sorted by capital
capital w =
4
linear scan
· profits
round
2
/2
funded:
c=0
+1
c=1
+2
c=1
+3
final capital = 4 (2 projects funded)
algo
master
.
io
Step:
3 projects, none funded yet
0 / 24
Input
Example 1
Example 2
Example 3
Custom
k
=
2
,
w
=
0
,
profits
=
[1, 2, 3]
,
capital
=
[0, 1, 1]
0 / 24
algo
master
.
io
Step:
3 projects, none funded yet
