Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Maximum Profit in Job Scheduling
Bookmark
Brute Force
Memoization
Bottom-Up DP
Input
Example 1
Example 2
Same Start
No Overlap
All Overlap
Custom
startTime
=
[1, 2, 3, 3]
,
endTime
=
[3, 4, 5, 6]
,
profit
=
[50, 10, 40, 70]
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
3-5
3-6
end
end
end
end
3-5
3-6
end
end
end
skip job 1, go to 2
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
3-5
3-6
end
end
end
end
3-5
3-6
end
end
end
solve(4): past the last job
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
3-5
3-6
end
$0
end
$0
end
end
3-5
3-6
end
end
end
nothing left to earn
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
3-5
3-6
$70
end
$0
end
$0
end
$0
end
3-5
3-6
end
end
end
nothing left to earn
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
$70
3-5
$70
3-6
$70
end
$0
end
$0
end
$0
end
$0
3-5
3-6
end
end
end
max($70, $10) = $70
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
$70
3-5
$70
3-6
$70
end
$0
end
$0
end
$0
end
$0
3-5
3-6
end
end
end
solve(3)
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
$70
3-5
$70
3-6
$70
end
$0
end
$0
end
$0
end
$0
3-5
3-6
end
$0
end
end
take job 3 for $70, then solve(4)
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
2-4
$70
3-5
$70
3-6
$70
end
$0
end
$0
end
$0
end
$0
3-5
3-6
$70
end
$0
end
$0
end
take job 2 for $40, then solve(4)
jobs (start-end, profit)
1-3 $50
2-4 $10
3-5 $40
3-6 $70
1-3
$120
2-4
$70
3-5
$70
3-6
$70
end
$0
end
$0
end
$0
end
$0
3-5
$70
3-6
$70
end
$0
end
$0
end
$0
best profit = $120
algo
master
.
io
Step:
4 jobs, each with a start, an end, and a profit. No two picked jobs may overlap
0 / 46
Input
Example 1
Example 2
Same Start
No Overlap
All Overlap
Custom
startTime
=
[1, 2, 3, 3]
,
endTime
=
[3, 4, 5, 6]
,
profit
=
[50, 10, 40, 70]
0 / 46
algo
master
.
io
Step:
4 jobs, each with a start, an end, and a profit. No two picked jobs may overlap
