Maximum Length Chain of Pairs

Problem Statement

You are given n pairs of numbers. In every pair, the first number is always smaller than the second. A chain of pairs can be formed if the second element of the previous pair is smaller than the first element of the next pair. Find the longest chain which can be formed.

Example:

• Input: pairs = {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90}}
• Output: 3 (The chain is {5, 24} -> {27, 40} -> {50, 90})

Noob-Friendly Explanation

Think of each pair as a time slot for an event — it starts at the first number and ends at the second. You want to attend as many events as possible, but you can only go to the next event if it starts AFTER the previous one has ended. What's the maximum number of events you can attend?

Approach 1: Brute Force

Intuition

Generate all possible subsets of pairs, check if each subset forms a valid chain, and return the length of the longest valid chain.

Algorithm

1. Sort pairs by the first element.
2. Use recursion to include or exclude each pair.
3. When including, make sure the chain remains valid.
4. Track the maximum chain length.

class Solution {
    public static int maxChainBrute(int[][] pairs, int index, int prevEnd) {
        if (index == pairs.length) return 0;

        // Exclude current pair
        int exclude = maxChainBrute(pairs, index + 1, prevEnd);

        // Include current pair if valid
        int include = 0;
        if (pairs[index][0] > prevEnd) {
            include = 1 + maxChainBrute(pairs, index + 1, pairs[index][1]);
        }

        return Math.max(include, exclude);
    }

    public static void main(String[] args) {
        int[][] pairs = {{5, 24}, {15, 28}, {27, 40}, {39, 60}, {50, 90}};
        java.util.Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        System.out.println(maxChainBrute(pairs, 0, Integer.MIN_VALUE)); // Output: 3
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - at each pair we choose include or exclude
• Space Complexity: O(n) - recursion stack depth

Approach 2: Optimal

Intuition

This is similar to the Longest Increasing Subsequence (LIS) problem. Sort pairs by the first element, then use DP where dp[i] is the length of the longest chain ending at pair i.

Algorithm

1. Sort pairs by the first element.
2. Create a dp array initialized to 1 (each pair alone is a chain of length 1).
3. For each pair i, check all previous pairs j. If pairs[j][1] < pairs[i][0], update dp[i] = max(dp[i], dp[j] + 1).
4. Return the maximum value in the dp array.

class Solution {
    public static int maxChainLength(int[][] pairs) {
        int n = pairs.length;

        // Sort by first element
        java.util.Arrays.sort(pairs, (a, b) -> a[0] - b[0]);

        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);

        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[][] pairs = {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90}};
        System.out.println(maxChainLength(pairs)); // Output: 3
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - two nested loops
• Space Complexity: O(n) - the dp array