Log inSign up
mediumLeetCodeNot Started

Maximum Length Chain of Pairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on LeetCode
Lesson

Problem Statement

You are given an array of N pairs pairs where pairs[i] = [left_i, right_i] and left_i < right_i.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this manner.

Return the length longest chain which can be formed. You do not need to use up all the given intervals, and pairs can be selected in any order.

Example 1 · Example 1: Three Disjoint Pairs:

Input: pairs = [[1, 2], [2, 3], [3, 4]]
Output: 2
Explanation: The longest chain is [1, 2] -> [3, 4]. Note [2, 3] cannot follow [1, 2] because 2 is not strictly greater than 2.

Example 2 · Example 2: Four Pairs:

Input: pairs = [[1, 2], [7, 8], [4, 5], [2, 3]]
Output: 3
Explanation: Sorted by end: [1, 2], [2, 3], [4, 5], [7, 8]. The chain is [1, 2] -> [4, 5] -> [7, 8] with length 3.

Constraints:

  • 1 <= pairs.length <= 104
  • -1000 <= left_i < right_i <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Map pair chaining directly to interval scheduling / activity selection.
  • Understand why sorting by end is strictly superior to sorting by start.
  • Implement the greedy solution across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Pairs [a, b] where chain requires previous end < next start.
  • Can pick any subset of pairs in any sequence.
  • Goal is to maximize the chain length.

Algorithmic Decision Tree:

  • Always sort by right coordinate pairs[i][1] ascending.
  • Advance currentEnd and increment length whenever pairs[i][0] > currentEnd.

Connected Patterns:

Activity SelectionNon-overlapping IntervalsLongest Increasing Subsequence

1. Recursive Subset Search

Intuition

Sort pairs by start coordinate, then recursively test including or excluding each pair while tracking the last chosen end coordinate.

Algorithm

  1. Step 1: Sort pairs ascending by start coordinate.
  2. Step 2: Define recursive function solve(idx, lastEnd).
  3. Step 3: If idx == n, return 0.
  4. Step 4: Compute notTake = solve(idx + 1, lastEnd).
  5. Step 5: If pairs[idx][0] > lastEnd, take = 1 + solve(idx + 1, pairs[idx][1]).
  6. Step 6: Return max(take, notTake).

Enumerate All Subsets of Pairs

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Pair [1,2] can be followed by [7,8] since 2 < 7
Visual state
Values and pointers at this exact step
intervals
P0
[1, 2]
P1
[7, 8]
P2
[4, 5]
chain["[1,2]","[7,8]"]
len2
maxLen2
Variables at this step
chain
["[1,2]","[7,8]"]
len
2
maxLen
2
Check / comparison
Test chain {[1,2], [7,8]}: 2 < 7
Decision / next transition
Valid chain of length 2.
Why this step matters

Pair [1,2] can be followed by [7,8] since 2 < 7.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int idx, int lastEnd, const vector<vector<int>>& pairs) {
9 if (idx == pairs.size()) return 0;
10 int notTake = solve(idx + 1, lastEnd, pairs);
11 int take = 0;
12 if (pairs[idx][0] > lastEnd) {
13 take = 1 + solve(idx + 1, pairs[idx][1], pairs);
14 }
15 return max(take, notTake);
16 }
17public:
18 int findLongestChain(vector<vector<int>>& pairs) {
19 sort(pairs.begin(), pairs.end());
20 return solve(0, -1e9, pairs);
21 }
22};
23
24int main() {
25 Solution sol;
26 vector<vector<int>> pairs = {{1, 2}, {7, 8}, {4, 5}, {2, 3}};
27 cout << "Longest Chain: " << sol.findLongestChain(pairs) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Longest Increasing Subsequence DP

Intuition

Sort pairs by start coordinate. Use an O(N2) dynamic programming table where dp[i] is the maximum chain length ending at pair i.

Algorithm

  1. Step 1: Sort pairs by first coordinate.
  2. Step 2: Initialize dp array of size n with all 1s.
  3. Step 3: For i from 1 to n - 1 and j from 0 to i - 1:
  4. Step 4: If pairs[j][1] < pairs[i][0], update dp[i] = max(dp[i], dp[j] + 1).
  5. Step 5: Return the maximum value in dp array.

Sort by Start Coordinate & LIS Dynamic Programming (O(N^2))

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Sorting gives monotonic ordering on starts, enabling LIS DP
Visual state
Values and pointers at this exact step
intervals
P0
[1, 2]
↑ i=0
P1
[4, 5]
P2
[7, 8]
i0
dp[1,1,1]
Variables at this step
i
0
dp
[1,1,1]
Check / comparison
Sort pairs by start coordinate: [1,2], [4,5], [7,8]. Initialize dp = [1, 1, 1]
Decision / next transition
dp[0] = 1 for base pair [1, 2].
Why this step matters

Sorting gives monotonic ordering on starts, enabling LIS DP.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findLongestChain(vector<vector<int>>& pairs) {
10 sort(pairs.begin(), pairs.end());
11 int n = pairs.size();
12 vector<int> dp(n, 1);
13 int maxLen = 1;
14
15 for (int i = 1; i < n; ++i) {
16 for (int j = 0; j < i; ++j) {
17 if (pairs[j][1] < pairs[i][0]) {
18 dp[i] = max(dp[i], dp[j] + 1);
19 }
20 }
21 maxLen = max(maxLen, dp[i]);
22 }
23
24 return maxLen;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> pairs = {{1, 2}, {7, 8}, {4, 5}, {2, 3}};
31 cout << "Longest Chain (DP): " << sol.findLongestChain(pairs) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2)
  • Space complexity: O(N)

3. Greedy Earliest Finish Time First

Intuition

Sort pairs ascending by the second element. Greedily select each compatible pair whose start is strictly greater than the current end coordinate.

Algorithm

  1. Step 1: Sort pairs in ascending order of their second coordinate pairs[i][1].
  2. Step 2: Initialize chain = 0 and currentEnd = -infinity.
  3. Step 3: Iterate through each pair [start, end] in sorted pairs.
  4. Step 4: If start > currentEnd, increment chain and update currentEnd = end.
  5. Step 5: Return chain.

Greedy Sort by End Coordinate (Interval Scheduling)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Greedy strategy: picking the pair that ends earliest leaves the maximal remaining room for future links
Visual state
Values and pointers at this exact step
intervals
P0
[1, 2]
↑ curr
P1
[4, 5]
P2
[7, 8]
currEnd2
chainLength1
i0
Variables at this step
currEnd
2
chainLength
1
i
0
Check / comparison
Sort by second coordinate (end): [1,2], [4,5], [7,8]
Decision / next transition
Pick P0 [1,2] first! Update currEnd = 2, chainLength = 1.
Why this step matters

Greedy strategy: picking the pair that ends earliest leaves the maximal remaining room for future links.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int findLongestChain(vector<vector<int>>& pairs) {
10 sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
11 return a[1] < b[1];
12 });
13
14 int chain = 0;
15 int currentEnd = -1e9;
16
17 for (const auto& p : pairs) {
18 if (p[0] > currentEnd) {
19 chain++;
20 currentEnd = p[1];
21 }
22 }
23
24 return chain;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> pairs = {{1, 2}, {7, 8}, {4, 5}, {2, 3}};
31 cout << "Longest Chain (Greedy): " << sol.findLongestChain(pairs) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Exponential Subset SearchO(2^N)O(N)Recursively consider including or excluding each pair after sorting by start, ensuring the chaining condition is met.Testing all 2N subsets.
2.Better — Longest Increasing Subsequence DPO(N^2)O(N)Sort pairs by first coordinate. Let dp[i] be the max chain length ending at pair i. dp[i] = 1 + max(dp[j]) for all j < i with pairs[j][1] < pairs[i][0].Nested inner loop scan.
3.Optimal — Greedy Earliest Finish TimeOptimalO(N log N)O(1) auxiliarySort pairs ascending by their right coordinate. Greedily pick the first pair. Iterate: if pair[0] > lastEnd, increment chain and update lastEnd.Sorting operation.
Back to DSA Sheet