Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Maximum Profit in Job Scheduling
Bookmark
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 =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
0
1
2
3
pick non-overlapping jobs to maximize total profit
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
0
1
2
3
pick non-overlapping jobs to maximize total profit
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
0
1
2
3
sort by end time
earlier-finishing jobs move up
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
1
2
3
i = 1
job 1
runs 2 to 4, pays
10
: take it or skip it?
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
1
2
3
i = 1
no job ends by t=2
: take =
10
alone
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
50
1
2
3
i = 1
dp[1] = max(
take 10
,
skip 50
) =
50
skip the job
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
50
1
2
3
i = 2
take =
40
+ dp[
0
] =
40
+
50
=
90
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
50
1
90
2
3
i = 2
dp[2] = max(
take 90
,
skip 50
) =
90
take the job
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
50
1
90
2
3
i = 3
job 3
runs 3 to 6, pays
70
: take it or skip it?
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
50
1
90
2
120
3
i = 3
dp[3] = max(
take 120
,
skip 90
) =
120
take the job
jobs =
4
1
2
3
4
5
6
50
0
10
1
40
2
70
3
dp
50
0
50
1
90
2
120
3
max profit =
120
= 50 + 70
algo
master
.
io
Step:
4 jobs, each with a start, an end, and a profit. No two picked jobs may overlap
0 / 12
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 / 12
algo
master
.
io
Step:
4 jobs, each with a start, an end, and a profit. No two picked jobs may overlap
