Skip to content

646. Maximum Length of Pair Chain

On LeetCode ->

Problem

Given pairs [left, right], find the maximum number that can be ordered into a chain where each pair's right value is strictly less than the next pair's left value. Pairs may be reordered or skipped.

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

Key trick

This is interval scheduling: sort pairs by their right endpoint, then greedily choose every pair that starts after the end of the last chosen pair.

Trap

  • The condition is strict: previous_end < start; touching pairs cannot be chained.
  • Sorting by the left endpoint and greedily selecting pairs can miss shorter pairs that leave more room.
  • The sort mutates the input if pairs.sort(...) is used.

Why is it interesting?

It resembles longest increasing subsequence and dynamic programming, but the earliest-finish greedy strategy reduces the solution to sorting and one scan.

Python solution

class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        # Finishing earlier leaves the most room for subsequent pairs.
        pairs.sort(key=lambda pair: pair[1])

        ans = 0
        prev_end = float("-inf")

        for start, end in pairs:
            if prev_end < start:
                ans += 1
                prev_end = end

        return ans

Time complexity: \(O(n \log n)\).

Auxiliary space complexity: \(O(1)\), excluding the sorting implementation's internal space.

Comment on my solution

Your dynamic programming approach is correct under the stated coordinate bounds, including the strict inequality implemented by range(start + x).

  • It unnecessarily scans a coordinate array for every pair.
  • It hard-codes the [-1000, 1000] constraint, so it is not robust to wider values.
  • Creating lengths_before_start adds avoidable allocations.
  • The problem has a simpler greedy solution with \(O(n \log n)\) time and \(O(1)\) auxiliary space.
  • Both your solution and the greedy version mutate pairs by sorting it in place.
# Ideas:
# - It reminds me of classic LIS longest increasing subsequence
#   - this uses an array of tails
# - we could use a custom comparator to sort the pairs
# - sort pairs first
#   - by the first pair element
# [[0,6],[1,2],[7,8],[4,5]]
# [[0,6],[1,2],[3,7],[4,5],[7,8]]
# [1,3] [4,7]
#       [3,5] [6,8] [9,10]

# WORKS
class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        n = len(pairs)
        pairs.sort(key=lambda p: p[1])
        x = 1000
        lengths = [0] * (2 * x + 1)
        for start, end in pairs:
            # max length of a chain ending at an inferior pair that can be chain
            lengths_before_start = [lengths[i] for i in range(start + x)]
            max_length = max(lengths_before_start) if lengths_before_start else 0
            lengths[end + x] = max(lengths[end + x], max_length + 1)
        return max(lengths)