Maximum Length of Pair Chain

The problem, simply

You get a list of pairs [left, right] with left < right. Pair [c, d] can follow pair [a, b] when b < c. You may pick pairs in any order and you do not have to use them all.

Give back the length of the longest chain you can build.

A story to remember it

Picture it

Examples

Way 1: the simple way

Sort the pairs by their start. Then for each pair, find the longest chain that ends with it, using the answers for the pairs before it. This is the same idea as the longest increasing subsequence.

1. Sort by the first number.
2. dp[i] starts at 1: the pair alone.
3. For every earlier pair j with pairs[j][1] < pairs[i][0], try dp[j] + 1.
4. The answer is the biggest dp[i].

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (p, q) -> Integer.compare(p[0], q[0]));   // sort by start
        int[] dp = new int[n];
        int best = 0;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;                                       // this pair alone
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) {             // j ends before i starts
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

How long it takes: each pair looks back at every earlier pair, O(n^2). Extra room: the dp row, O(n).

Way 2: the clever way

Watch the show that ends soonest. Sort by the end and walk once.

1. Sort pairs by the second number.
2. Keep end, where the chain currently ends. Nothing is chosen yet.
3. For each pair, if its start is bigger than end, add it to the chain and set end to its right side. Otherwise skip it.

Why it is safe: in any best chain, swap the first pair for the pair that ends earliest overall. It ends no later, so the rest of the chain still fits after it. Do the same for the next spot, and the next. The greedy chain is never shorter.

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (p, q) -> Integer.compare(p[1], q[1]));   // soonest end first
        int count = 0;
        long end = Long.MIN_VALUE;           // the chain has not started
        for (int[] p : pairs) {
            if (p[0] > end) {                // fits after the chain
                count++;
                end = p[1];
            }
        }
        return count;
    }
}

How long it takes: sorting is O(n log n) and the walk is O(n). Extra room: two numbers, O(1), apart from what the sort itself needs.

Watch out for

• Sort by the end, not the start, for the greedy.
• The follow rule is strict: b < c.
• Comparators written as p[1] - q[1] can overflow on big negative and positive numbers. Use Integer.compare.

What interviewers ask next

• Why does greedy work here but not for "maximum total weight"? Weights break the swap argument: the earliest ending pair could be worth very little. Use DP plus binary search, as in weighted job scheduling.
• How many pairs must you remove so none overlap? n minus the longest chain (non-overlapping intervals).
• How many arrows burst all balloons? Same sort by end, but touching counts as overlapping there.
• Can Way 1 be O(n log n)? Yes, with a sorted list of chain ends and binary search, like the fast longest increasing subsequence.

Remember this

Grown-up words: the shows are intervals, choosing the soonest end is the activity selection greedy, swapping into a best chain is an exchange argument, and Way 1 is the longest increasing subsequence DP.