LeetCode 646: Maximum Length of Pair Chain

Problem Restatement

We are given a list of integer pairs.

Each pair looks like:

[left, right]

A pair:

[a, b]

can be followed by:

[c, d]

if:

b < c

We need to build the longest possible chain of pairs.

Return the maximum chain length.

The constraints guarantee:

left < right

for every pair.

Input and Output

Example function shape:

def findLongestChain(pairs: list[list[int]]) -> int:
    ...

Examples

Example 1:

pairs = [[1, 2], [2, 3], [3, 4]]

Possible chains:

The best chain is:

[1,2] -> [3,4]

Length:

2

Example 2:

pairs = [[1, 2], [7, 8], [4, 5]]

We can chain all three:

[1,2] -> [4,5] -> [7,8]

So the answer is:

3

First Thought: Try All Chains

A brute force solution would try every subset and every ordering.

This is too expensive because the number of possible chains grows exponentially.

We need to recognize the structure of the problem.

Key Insight

This problem is almost identical to interval scheduling.

Each pair behaves like an interval:

[start, end]

To maximize how many intervals we can take, the classic greedy strategy is:

Always choose the interval with the smallest ending value first.

Why?

A smaller ending value leaves more room for future pairs.

So:

1. Sort pairs by their second value.
2. Greedily pick pairs whenever they can extend the current chain.

Why Sorting by End Works

Suppose we have:

[1, 10]
[2, 3]
[4, 5]

If we choose [1,10] first, we cannot take anything else.

But if we choose the pair with the smallest ending value first:

[2,3]

then we can also take:

[4,5]

This gives a longer chain.

Algorithm

1. Sort pairs by their second value.
2. Initialize:
   1. count = 0
   2. current_end = -infinity
3. Scan the sorted pairs:
   1. If the current pair starts after current_end, take it.
   2. Increase count.
   3. Update current_end.
4. Return count.

Implementation

class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort(key=lambda pair: pair[1])

        count = 0
        current_end = float("-inf")

        for left, right in pairs:
            if current_end < left:
                count += 1
                current_end = right

        return count

Code Explanation

First, we sort by the ending value:

pairs.sort(key=lambda pair: pair[1])

This ensures we always consider the earliest-finishing pair first.

We track the end value of the last chosen pair:

current_end = float("-inf")

Initially, any pair can be chosen.

For each pair:

if current_end < left:

If the current pair starts after the previous chosen pair ends, it can extend the chain.

So we take it:

count += 1
current_end = right

At the end, count is the maximum chain length.

Correctness

The algorithm always selects the available pair with the smallest ending value.

Suppose the algorithm selects pair A, while some optimal solution selects a different compatible pair B first.

Because the pairs are sorted by ending value, the end of A is less than or equal to the end of B.

Therefore, replacing B with A cannot reduce the number of future pairs that can still be chosen, since A finishes no later than B.

So every optimal solution can be transformed into another optimal solution that begins with the greedy choice.

After choosing the first pair, the remaining problem has the same structure: find the maximum chain among pairs starting after the chosen end value.

By repeatedly applying the same argument, the greedy algorithm constructs an optimal chain.

Therefore, the returned chain length is maximum.

Complexity

Let n = len(pairs).

Alternative Solution: Dynamic Programming

We can also use DP.

Sort pairs by start value.

Let:

dp[i]

mean:

maximum chain length ending at pair i

Transition:

if pairs[j][1] < pairs[i][0]:
    dp[i] = max(dp[i], dp[j] + 1)

Implementation:

class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort()

        n = len(pairs)
        dp = [1] * n

        for i in range(n):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)

        return max(dp)

The greedy solution is simpler and faster.

Connection to Activity Selection

This problem is the same core structure as:

The key pattern is:

When maximizing the number of non-overlapping intervals, sort by ending time.

Testing

def run_tests():
    s = Solution()

    assert s.findLongestChain([[1, 2], [2, 3], [3, 4]]) == 2
    assert s.findLongestChain([[1, 2], [7, 8], [4, 5]]) == 3
    assert s.findLongestChain([[1, 10], [2, 3], [4, 5]]) == 2
    assert s.findLongestChain([[5, 24], [15, 25], [27, 40], [50, 60]]) == 3
    assert s.findLongestChain([[-10, -1], [0, 2], [3, 5]]) == 3
    assert s.findLongestChain([[1, 100]]) == 1

    print("all tests passed")

run_tests()

Test meaning: