Solution Explanation for Maximum Length of Pair Chain

This problem asks to find the length of the longest chain that can be formed from a given set of pairs, where a pair (c, d) follows another pair (a, b) if b < c. This suggests a greedy approach or dynamic programming. The most efficient solution uses a greedy strategy combined with sorting.

Approach: Greedy with Sorting

1. Sort by End Time: The core idea is to sort the pairs based on their second element (the right endpoint). Sorting ensures that we consider pairs in a way that allows us to extend chains efficiently. We sort in ascending order of the right endpoints ( right_i).

2. Iterative Greedy Selection: We iterate through the sorted pairs. We maintain a variable pre to keep track of the end time of the last selected pair in the current chain.

3. Chain Extension: For each pair [left_i, right_i], we check if its start time (left_i) is greater than the end time of the last selected pair (pre). If it is, it means we can extend the current chain. We increment the chain length (ans) and update pre to right_i to reflect the new end time of the extended chain.

4. Return Length: After processing all pairs, the value of ans represents the length of the longest chain formed.

Time and Space Complexity

• Time Complexity: O(n log n), dominated by the sorting step. The iteration through the sorted pairs takes O(n) time.
• Space Complexity: O(log n) or O(n), depending on the sorting implementation. In-place sorting algorithms like quicksort or mergesort have O(log n) space complexity in the average case and O(n) in the worst case. Some implementations might use extra space to store a sorted copy.

Code Examples (with explanations inline)

The code examples below demonstrate the solution in several popular programming languages. The core logic remains consistent across all languages.

Python

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        # Sort pairs by the second element (end time)
        pairs.sort(key=lambda x: x[1])  
        ans = 0  # Length of the longest chain
        pre = float('-inf')  # End time of the last selected pair (initialized to negative infinity)
        for a, b in pairs: # Iterate through the sorted pairs
            if pre < a:  # Check if the current pair's start time is greater than the previous pair's end time
                ans += 1  # Extend the chain
                pre = b  # Update the end time of the last selected pair
        return ans

Java

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[1], b[1])); // Sort by the second element
        int ans = 0; // Length of the longest chain
        int pre = Integer.MIN_VALUE; // End time of the last selected pair
        for (int[] p : pairs) { // Iterate through the sorted pairs
            if (pre < p[0]) { // Check if the current pair can extend the chain
                ans++; // Extend the chain
                pre = p[1]; // Update the end time
            }
        }
        return ans;
    }
}

The other languages (C++, Go, TypeScript, Rust) follow a very similar structure, differing only in syntax and specific library functions used for sorting and comparison. The core algorithmic idea remains the same.