Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Maximum Length of Pair Chain
Bookmark
Dynamic Programming
Greedy
Input
Standard
Non-overlapping
Large
Custom
pairs
=
[[-10,-8],[8,9],[-5,0],[6,10],[-6,-4],[1,7],[9,10],[-4,7]]
Pairs Sorted by Start
dp
Pairs Sorted by Start
dp
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
Pair 2 is [-5,0]
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
1
[-4,7]
1
[1,7]
1
[6,10]
1
[8,9]
1
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
-4 is not below -4, so pair 1 overlaps
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
1
[6,10]
1
[8,9]
1
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
dp[4] = max(dp[4], dp[1] + 1) = 3
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
1
[8,9]
1
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
dp[5] = max(dp[5], dp[0] + 1) = 2
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
2
[8,9]
1
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
Pair 6 is [8,9]
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
3
[8,9]
1
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
dp[6] = max(dp[6], dp[2] + 1) = 3
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
3
[8,9]
3
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
Pair 7 is [9,10]
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
3
[8,9]
4
[9,10]
1
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
7 < 9, so pair 3 can come first
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
3
[8,9]
4
[9,10]
3
Pairs Sorted by Start
0
[-10,-8]
1
[-6,-4]
2
[-5,0]
3
[-4,7]
4
[1,7]
5
[6,10]
6
[8,9]
7
[9,10]
Longest chain is 4
dp
[-10,-8]
1
[-6,-4]
2
[-5,0]
2
[-4,7]
2
[1,7]
3
[6,10]
3
[8,9]
4
[9,10]
4
algo
master
.
io
Step:
8 pairs. A chain needs each pair to start after the previous one ends.
0 / 57
Input
Standard
Non-overlapping
Large
Custom
pairs
=
[[-10,-8],[8,9],[-5,0],[6,10],[-6,-4],[1,7],[9,10],[-4,7]]
0 / 57
algo
master
.
io
Step:
8 pairs. A chain needs each pair to start after the previous one ends.
