Maximum Length of Pair Chain

Maximum Length of Pair Chain

What is this problem about?

The Maximum Length of Pair Chain coding problem gives you a collection of pairs [a, b] where a < b. You can chain pairs such that for consecutive pairs [a,b] and [c,d] in the chain, b < c (the end of the previous pair must be strictly less than the start of the next). Find the maximum number of pairs you can chain together.

Why is this asked in interviews?

Apple, Google, Amazon, and Swiggy use this problem to test classic greedy vs DP reasoning. It is the interval scheduling problem in disguise. Candidates familiar with the activity selection problem can immediately apply the greedy approach (sort by end point, greedily select non-overlapping intervals). Others may reach for DP, which also works but is less efficient. Recognizing the greedy insight earns extra points.

Algorithmic pattern used

The optimal solution uses greedy sorting by end point. Sort all pairs by their second element (the end). Greedily include a pair if its start is strictly greater than the end of the last included pair. This is identical to the classic interval scheduling maximization. Time complexity: O(n log n) for sorting, O(n) for the greedy scan.

A DP approach: sort by start, define dp[i] = max chain length ending with pair i, transition: dp[i] = max(dp[j] + 1) for all j where pairs[j][1] < pairs[i][0]. This is O(n²) DP or O(n log n) with binary search (similar to patience sorting for LIS).

Example explanation

Pairs: [[1,2], [2,3], [3,4]]

• Sort by end: [[1,2], [2,3], [3,4]] (already sorted).
• Select [1,2]. Last end = 2.
• [2,3]: start=2 is NOT > 2. Skip.
• [3,4]: start=3 > 2. Select. Last end = 4.
• Chain length = 2.

Note: [1,2] → [3,4] forms a valid chain since 2 < 3.

Common mistakes candidates make

• Using non-strict inequality: The condition is b < c (strict), not b ≤ c. Using ≤ incorrectly includes overlapping pairs.
• Sorting by start instead of end: This is the crucial difference between greedy interval scheduling and a naive approach. Sorting by start doesn't yield a greedy solution.
• Confusing with the "Merge Intervals" problem: Here you maximize the chain count; don't merge — select non-overlapping greedily.

Interview preparation tip

For the Array Sorting Greedy Dynamic Programming interview pattern, memorize the interval scheduling greedy rule: "sort by end time, always pick the interval that ends earliest among valid options." This applies to Maximum Length of Pair Chain, the activity selection problem, and many scheduling interview questions at top tech companies.