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:
- Sort all pairs by their second element (ending value)
- Pick the first pair (it has the smallest end)
- For each remaining pair, if its start is greater than your last pair's end, add it to the chain
- 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.