Introduction

The longest chain of pairs problem asks you to find the maximum number of pairs (a, b) you can chain together so that each next pair starts after the previous pair ends. Formally, given pairs where each has a start a and end b, find the longest sequence where b_i < a_{i+1} for every consecutive pair. This is equivalent to the activity selection problem and appears in scheduling, bioinformatics sequence alignment, and interval optimization.

Problem Definition

Given n pairs where each pair is (a, b) with a < b, select the longest subsequence of pairs such that for consecutive selected pairs (a_i, b_i) and (a_j, b_j), the condition b_i < a_j holds.

# Example input
pairs = [(5, 24), (15, 25), (27, 40), (50, 60)]
# Longest chain: (5,24) -> (27,40) -> (50,60) = length 3

Greedy Approach (Optimal)

Sort pairs by their second element (end value), then greedily pick each pair whose start is greater than the previous selected pair's end. This is the same logic as the classic activity selection problem.

1def longest_chain_greedy(pairs):
2    pairs.sort(key=lambda p: p[1])
3
4    count = 1
5    current_end = pairs[0][1]
6
7    for i in range(1, len(pairs)):
8        if pairs[i][0] > current_end:
9            count += 1
10            current_end = pairs[i][1]
11
12    return count
13
14
15pairs = [(5, 24), (39, 60), (15, 28), (27, 40), (50, 90)]
16print(longest_chain_greedy(pairs))  # 3

Sorting by end value ensures that each selection leaves the most room for future pairs. This runs in O(n log n) time due to sorting and O(1) extra space.

Why Sort by End, Not Start

Sorting by start value can lead to suboptimal chains. A pair with a small start but large end blocks many future pairs. Sorting by end minimizes the "footprint" of each selected pair.

1# Sorting by start: [(1,100), (2,3), (4,5)]
2# Greedy picks (1,100) first -> chain length 1
3
4# Sorting by end: [(2,3), (4,5), (1,100)]
5# Greedy picks (2,3) then (4,5) -> chain length 2

Dynamic Programming Approach

If you need the actual chain (not just the length), or want to understand the DP formulation, define dp[i] as the length of the longest chain ending with pair i.

1def longest_chain_dp(pairs):
2    pairs.sort(key=lambda p: p[0])
3    n = len(pairs)
4    dp = [1] * n
5
6    for i in range(1, n):
7        for j in range(i):
8            if pairs[j][1] < pairs[i][0]:
9                dp[i] = max(dp[i], dp[j] + 1)
10
11    return max(dp)
12
13
14pairs = [(5, 24), (39, 60), (15, 28), (27, 40), (50, 90)]
15print(longest_chain_dp(pairs))  # 3

This runs in O(n^2) time and O(n) space. It is slower than greedy but generalizes to variants where the selection criterion is more complex.

Reconstructing the Chain

To recover the actual pairs in the chain, track predecessors during DP.

1def longest_chain_with_path(pairs):
2    indexed = sorted(enumerate(pairs), key=lambda x: x[1][0])
3    n = len(indexed)
4    dp = [1] * n
5    prev = [-1] * n
6
7    for i in range(1, n):
8        for j in range(i):
9            if indexed[j][1][1] < indexed[i][1][0] and dp[j] + 1 > dp[i]:
10                dp[i] = dp[j] + 1
11                prev[i] = j
12
13    best = max(range(n), key=lambda i: dp[i])
14    chain = []
15    while best != -1:
16        chain.append(indexed[best][1])
17        best = prev[best]
18
19    return list(reversed(chain))
20
21
22pairs = [(5, 24), (39, 60), (15, 28), (27, 40), (50, 90)]
23print(longest_chain_with_path(pairs))
24# [(5, 24), (27, 40), (50, 90)]

Comparison

Use greedy when you only need the count. Use DP when you need the actual selected pairs or when the selection rule has additional constraints.

Common Pitfalls

• Sorting by the first element instead of the second, which produces suboptimal greedy results.
• Using >= instead of > in the chain condition — the problem requires strict inequality b_i < a_j, not b_i <= a_j.
• Forgetting to handle the single-pair base case where the answer is always 1.
• Confusing this with Longest Increasing Subsequence — LIS operates on single values, not pairs with start/end.
• Returning dp[-1] instead of max(dp) — the longest chain may not end at the last sorted pair.

Summary

• Sort pairs by end value and apply greedy selection for O(n log n) optimal length.
• Use DP with O(n^2) time when you need to reconstruct the actual chain or handle custom constraints.
• The problem is equivalent to activity selection and maximum non-overlapping intervals.
• Always use strict inequality b_i < a_j for chain validity.
• Greedy by end value is provably optimal for the standard formulation.