Domain 2MediumCORE

Maximum Length of Pair Chain

We are given a list of intervals (pairs) where each pair [a, b] satisfies a < b. We need to construct the longest possible sequence of pairs such that for any two consecutive pairs (a, b) and (c, d), the end of the first is strictly less than the start of the second (b < c).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

646. Maximum Length of Pair Chain

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 1
Acceptance rate: 53.1%


Problem Breakdown

We are given a list of intervals (pairs) where each pair [a, b] satisfies a < b. We need to construct the longest possible sequence of pairs such that for any two consecutive pairs (a, b) and (c, d), the end of the first is strictly less than the start of the second (b < c).

Inputs: A list of lists pairs (e.g., [[1,2], [2,3]]). Outputs: An integer representing the maximum length of such a chain. Constraints & Edge Cases:

  • NN is between 1 and 1000.
  • Pairs can be reordered; we don’t need to use all pairs.
  • Values can be negative or large, but standard integer types handle this.
  • Strict inequality (b < c) means touching intervals (e.g., [1,2] and [2,3]) cannot chain together.

Intuition

Initially, one might think of Dynamic Programming where dp[i] represents the max chain length ending at index i. We would iterate through all previous pairs to find valid predecessors. This is an O(N2)O(N^2) approach. While acceptable for N=1000N=1000, it’s not optimal.

However, this problem maps directly to the classic Interval Scheduling Maximization problem. The key insight is that to maximize the number of non-overlapping intervals we can pick, we should always prioritize picking the interval that finishes earliest. Why? Because an interval that ends earlier leaves more “room” for subsequent intervals to fit in.

So, instead of checking all combinations or using DP, we can sort the pairs by their end times and greedily select them if they don’t conflict with our last selected pair. This transforms the problem into a linear scan after sorting.

Approach

  1. Sort: Sort the input list of pairs based on the second element (the end value) in ascending order.
  2. Iterate & Select: Initialize a counter for the chain length and a variable to track the last_end time of the last selected pair.
  3. Greedy Check: For each pair in the sorted list, check if its start value is strictly greater than last_end.
    • If yes: Include this pair in the chain, increment the counter, and update last_end to the current pair’s end value.
    • If no: Skip the pair (it overlaps with our current chain).
  4. Return: Return the final count.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N). Sorting takes O(Nlog⁡N)O(N \log N), and the linear scan takes O(N)O(N).
  • Space Complexity: O(1)O(1) auxiliary space (ignoring the space required for sorting in Python’s Timsort which is technically O(N)O(N)).

Solution

def findLongestChain(pairs):
    # Sort pairs by their end value to enable greedy selection
    pairs.sort(key=lambda x: x[1])
    
    chain_length = 0
    last_end = float('-inf')
    
    for start, end in pairs:
        # If the current pair starts after the last selected pair ends
        if start > last_end:
            chain_length += 1
            last_end = end
            
    return chain_length

Edge Cases Handled

  • Empty Input: Though constraints say N≥1N \ge 1, the loop naturally returns 0 if the list is empty.
  • Single Pair: The loop runs once, start > -inf is true, returns 1.
  • Strict Overlap: Pairs like [1,2] and [2,3] are correctly skipped because 2 > 2 evaluates to False.
  • Negative Numbers: Logic holds as long as comparison operators work (Python handles signed integers correctly).