Maximum Length of Pair Chain

Problem Statement

You are given n pairs of integers. In each pair, the first number is always smaller than the second number. A pair (a, b) can follow pair (c, d) if b < c (the second number of the previous pair is less than the first number of the next pair). Find the longest chain of pairs you can form.

Example:

• Input: pairs = [[1,2], [2,3], [3,4]]

• Output: 2

• Explanation: The longest chain is [1,2] -> [3,4]. We can't use [2,3] after [1,2] because 2 is not less than 2.

• Input: pairs = [[1,2], [7,8], [4,5]]

• Output: 3

• Explanation: Sort by second element: [1,2], [4,5], [7,8]. All three can chain: 2 < 4 < 7.

Noob-Friendly Explanation

Imagine you have several time slots (like meetings) with start and end times. You want to attend as many meetings as possible, but you can only go to the next meeting if it starts after your current one ends (not at the same time, strictly after).

For example, if you attend a meeting from 1-2, you can attend one starting at 3 but not one starting at 2. How many meetings can you fit?

Approach 1: Brute Force (Recursion)

Intuition

Try all possible combinations of pairs. For each pair, decide whether to include it in the chain or skip it.

Algorithm

1. Sort pairs by the first element.
2. For each pair, try including it (if it follows the chain) or skipping it.
3. Return the maximum chain length.

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        return solve(pairs, 0, Integer.MIN_VALUE);
    }

    private int solve(int[][] pairs, int index, int prevEnd) {
        if (index == pairs.length) return 0;

        // Skip this pair
        int skip = solve(pairs, index + 1, prevEnd);

        // Include this pair if possible
        int include = 0;
        if (pairs[index][0] > prevEnd) {
            include = 1 + solve(pairs, index + 1, pairs[index][1]);
        }

        return Math.max(skip, include);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - At each pair, we branch into two choices.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Greedy)

Intuition

This is similar to the activity selection problem. Sort pairs by their second element (end value). Greedily pick the pair with the smallest end that doesn't conflict with the last picked pair. This leaves maximum room for future pairs.

Algorithm

1. Sort pairs by the second element.
2. Pick the first pair. Set currentEnd = pair[1].
3. For each subsequent pair, if pair[0] > currentEnd, pick it and update currentEnd.
4. Count the total pairs picked.

import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        // Sort by the second element (end value)
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        int count = 1;
        int currentEnd = pairs[0][1];

        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > currentEnd) {
                count++;
                currentEnd = pairs[i][1];
            }
        }

        return count;
    }
}

Complexity Analysis

• Time Complexity: O(n log n) - Sorting takes O(n log n), and the greedy scan is O(n).
• Space Complexity: O(1) - Only a few variables (sorting is in-place).