Course contentsShow
← Computer Science
Lesson 897 of 2,87221. Greedy AlgorithmsFree lesson

Maximum Length Chain of Pairs

Find longest chain where each pair's second element is less than the next pair's first element.

Maximum Length Chain of Pairs

What you'll learn: How to find the longest chain of pairs where pairs can connect end-to-start like links in a chain.

The Problem

Imagine you have pairs of numbers like (a, b) representing intervals or ranges. You want to build the longest possible "chain" where each pair connects to the next: specifically, the second element of one pair must be less than the first element of the next pair.

For example, with pairs (5, 24), (15, 25), (27, 40), and (50, 60), you could chain (5, 24) → (27, 40) → (50, 60) for a length of 3, because 24 < 27 and 40 < 50.

The Greedy Strategy

This is a classic greedy problem similar to Activity Selection. The key insight: always pick the pair with the smallest ending value that doesn't conflict with your current chain. Why? Because a smaller ending value leaves more "room" for future pairs to fit.

Algorithm:

  1. Sort all pairs by their second element (ending value)
  2. Pick the first pair (it has the smallest end)
  3. For each remaining pair, if its start is greater than your last pair's end, add it to the chain
  4. Count how many pairs you selected

Think of it like scheduling activities that end as early as possible—you maximize opportunities for more activities later.

Why This Works

By always choosing the pair that ends earliest, you're being optimally "greedy" about freeing up space. Any other choice would only reduce your future options. This satisfies the greedy choice property and leads to an optimal solution.

Key Takeaway: Sort pairs by ending value and greedily select non-conflicting pairs that finish earliest to build the longest chain—a direct application of interval scheduling.