Code Implementation

class Solution:
    def findLongestChain(self, pairs):
        pairs.sort(key=lambda x: x[1])
        curr = float('-inf')
        count = 0
        for pair in pairs:
            if pair[0] > curr:
                count += 1
                curr = pair[1]
        return count
      

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[1] < b[1];
        });
        int curr = INT_MIN, count = 0;
        for (const auto& pair : pairs) {
            if (pair[0] > curr) {
                count++;
                curr = pair[1];
            }
        }
        return count;
    }
};
      

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1]));
        int curr = Integer.MIN_VALUE, count = 0;
        for (int[] pair : pairs) {
            if (pair[0] > curr) {
                count++;
                curr = pair[1];
            }
        }
        return count;
    }
}
      

var findLongestChain = function(pairs) {
    pairs.sort((a, b) => a[1] - b[1]);
    let curr = -Infinity, count = 0;
    for (let pair of pairs) {
        if (pair[0] > curr) {
            count++;
            curr = pair[1];
        }
    }
    return count;
};
      

Problem Description

Given a list of pairs where each pair is a list of two integers [a, b] with a < b, you are to find the length of the longest chain you can form. A chain is a sequence of pairs (p1, p2, ..., pn) such that for every consecutive pair, the condition p1[1] < p2[0] holds. Each pair can be used at most once in the chain. Return the maximum possible length of such a chain.

• You must not reuse elements; each pair is used at most once.
• There may be multiple valid chains, but you must return the length of the longest.
• Input: pairs is a list of integer pairs, e.g. [[1,2],[2,3],[3,4]].
• Output: Integer representing the maximum chain length.

Thought Process

Initially, you might consider brute-forcing all possible sequences of pairs to find the longest valid chain. This would involve checking every combination, which quickly becomes infeasible as the number of pairs increases.

To optimize, notice that this problem is similar to the activity selection problem: you want to select the most pairs such that each pair's start is after the previous pair's end. This hints at a greedy or dynamic programming solution, where the key is to make choices that leave as much room as possible for future pairs.

The major insight is that by always choosing the next pair with the smallest possible end value (that is still valid), you maximize the number of pairs you can chain. Sorting the pairs by their second value enables this greedy selection.

Solution Approach

• Step 1: Sort the pairs by their ending value.
  • This ensures that when building the chain, you always pick the pair that leaves the most "room" for subsequent pairs.
• Step 2: Initialize variables.
  • Keep a variable (e.g., curr) to track the end of the last selected pair (initially negative infinity).
  • Keep a counter (count) for the length of the chain.
• Step 3: Iterate through the sorted pairs.
  • For each pair, if its start value is greater than the end value of the last selected pair, add it to the chain (increment count and update curr).
  • If not, skip it and continue to the next pair.
• Step 4: Return the count.
  • This count is the maximum length of a chain you can form.

This greedy algorithm works because, by always picking the earliest finishing pair, you keep the most options available for subsequent selections, just like scheduling the most non-overlapping activities.

Example Walkthrough

Let's use the input pairs = [[1,2], [2,3], [3,4]].

1. Sort pairs by their end: [[1,2], [2,3], [3,4]] (already sorted).
2. Initialize curr = -inf, count = 0.
3. First pair: [1,2]. Since 1 > -inf, include it. Now curr = 2, count = 1.
4. Second pair: [2,3]. 2 > 2 is false, so skip.
5. Third pair: [3,4]. 3 > 2 is true, include it. Now curr = 4, count = 2.
6. No more pairs. Final answer: 2.

The longest chain is [1,2] → [3,4].

Time and Space Complexity

• Brute-force approach:
  • Would try every possible subset and order of pairs, leading to exponential time complexity: O(2^n \cdot n!).
• Optimized (greedy) approach:
  • Sorting the pairs: O(n \log n).
  • Iterating through pairs: O(n).
  • Total time: O(n \log n).
  • Space: O(1) extra (if sorting in place), or O(n) if sorting makes a copy.

Summary

The Maximum Length of Pair Chain problem is elegantly solved by sorting the pairs by their end values and greedily selecting the next valid pair. This approach is inspired by the activity selection problem and ensures that at each step, you maximize the number of pairs you can include in the chain. The result is a simple, efficient algorithm with O(n \log n) time complexity, making it both practical and optimal.