Maximum Length of Pair Chain

How it works

This problem is identical to the classic interval scheduling problem. By sorting pairs by their end values, we can greedily select pairs. The key insight is that choosing the pair with the smallest end value leaves the most room for subsequent pairs. Whenever we find a pair whose start is greater than our current chain's end, we add it to the chain.

Steps

1. Sort pairs by their second element (end value).
2. Initialize length = 1 and end = pairs[0][1] (start with the first pair).
3. Iterate through remaining pairs. If a pair's start is greater than end, increment length and update end to this pair's end value.
4. Return length.

Complexity

• Time complexity: O(nlog n)
• Space complexity: O(1) or O(n) depending on the sorting algorithm.

Things to watch for

Sorting by the Wrong Element

A common mistake is sorting pairs by their first element (start value) instead of the second element (end value) when using the greedy approach. Sorting by end values is crucial because it ensures we always pick the pair that leaves the most room for subsequent pairs. Sorting by start values can lead to suboptimal chains.

Using Non-Strict Inequality

The problem requires that for pair [c, d] to follow pair [a, b], we need b < c (strictly less than). Using b <= c instead will incorrectly allow pairs where the end of one equals the start of another, violating the chain condition.

Confusing with Longest Increasing Subsequence

While this problem resembles LIS, the chain condition b < c is different from the standard LIS comparison. Directly applying LIS logic without adapting for the pair structure will produce incorrect results. The binary search approach requires careful handling of which element to compare and which to store.

from typing import List

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda p: p[1])
        length = 1
        end = pairs[0][1]

        for i in range(1, len(pairs)):
            if end < pairs[i][0]:
                length += 1
                end = pairs[i][1]

        return length

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](const auto& a, const auto& b) {
            return a[1] < b[1];
        });

        int length = 1, end = pairs[0][1];

        for (int i = 1; i < pairs.size(); i++) {
            if (end < pairs[i][0]) {
                length++;
                end = pairs[i][1];
            }
        }

        return length;
    }
};