Maximum Length Chain of Pairs

The problem, simply

You get n pairs of numbers (a, b), and in every pair a < b. Pair (c, d) may come right after pair (a, b) in a chain only if b < c: the next one must start strictly after the last one ends.

You may use the pairs in any order and skip any you like. Give back the length of the longest chain.

A story to remember it

Picture it

Examples

Way 1: the simple way

Ask a question for each pair: "if my chain starts with this pair, how long can it get?" To answer it, try every pair that can come next and ask the same question about that one.

1. longestFrom(i) starts at 1, for pair i itself.
2. For every pair j with pairs[i][1] < pairs[j][0], try 1 + longestFrom(j).
3. The answer is the biggest longestFrom(i) over all starting pairs.

The letters match the picture: A is 24, B is 60, C is 28, D is 40 and E is 90.

class Solution {
    public int maxChainLen(int[][] pairs) {
        int best = 0;
        for (int i = 0; i < pairs.length; i++) {
            best = Math.max(best, longestFrom(pairs, i));   // try every first pair
        }
        return best;
    }

    private int longestFrom(int[][] pairs, int i) {
        int best = 1;                                        // pair i on its own
        for (int j = 0; j < pairs.length; j++) {
            if (pairs[i][1] < pairs[j][0]) {                 // j starts after i ends
                best = Math.max(best, 1 + longestFrom(pairs, j));
            }
        }
        return best;
    }
}

How long it takes: the same chains are explored again and again, which can grow like O(2^n). Extra room: the waiting calls, at most one per pair in a chain, O(n).

Way 2: the clever way

Be the smart camper. Sort the pairs by their end. Walk through them and take a pair whenever it starts after the end of the last pair you took.

1. Sort pairs by the second number.
2. Keep end, the end of the last pair taken. At the start nothing is taken.
3. For each pair: if its start is bigger than end, take it and move end to its end. Otherwise skip it.

Why is this safe? Look at any best chain. Swap its first pair for the pair that ends earliest of all. That pair ends no later, so everything after it still fits. The chain stays just as long. Repeat the same swap for the second pair, and so on.

import java.util.Arrays;

class Solution {
    public int maxChainLen(int[][] pairs) {
        Arrays.sort(pairs, (p, q) -> Integer.compare(p[1], q[1]));   // earliest end first
        int count = 0;
        long end = Long.MIN_VALUE;            // nothing taken yet
        for (int[] p : pairs) {
            if (p[0] > end) {                 // starts after the last one ends
                count++;
                end = p[1];
            }
        }
        return count;
    }
}

How long it takes: sorting is O(n log n), the walk is O(n). Extra room: two numbers, O(1), not counting the room the sort uses.

Way 3: the DP table

This page sits in the dynamic programming list, and interviewers often want this version too, because it still works when pairs have different values (a weight per pair).

Sort by start. dp[i] is the longest chain that ends with pair i. It is 1 plus the best dp[j] of an earlier pair j that ends before pair i starts.

import java.util.Arrays;

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

This takes O(n^2) time and O(n) extra room. It is the same idea as the longest increasing subsequence.

Watch out for

• The rule is strictly less than: b < c. A chain cannot reuse a touching end, so 2 then 3 is not allowed. Read the problem, some versions allow b <= c.
• a - b comparators can overflow on huge numbers. Use Integer.compare.
• An empty list gives 0, not 1.

What interviewers ask next

• Print the chain, not only its length. In the greedy, write down each pair you take.
• What if each pair has a value and you want the biggest total value? Greedy breaks. Use the DP table, and make it fast with binary search for the last pair that ends before the current start. That is weighted job scheduling.
• What is the fewest pairs to remove so no two overlap? It is n minus this answer.
• Can the DP version be O(n log n)? Yes, with the patience sorting trick from longest increasing subsequence, but the greedy is simpler.

Remember this

Grown-up words: the activities are intervals, picking the earliest finish is the activity selection greedy, the swap argument is an exchange argument, and the DP table is the longest increasing subsequence pattern.