Course4all
Join us on telegram
Home/dsa/Greedy/Maximum Length of Pair Chain

Maximum Length of Pair Chain

Master this topic with zero to advance depth.

Maximum Length of Pair Chain

You are given an array of n pairs pairs where pairs[i] = [left_i, right_i] and left_i < right_i.

A pair p2 follows p1 if p1[1] < p2[0]. Return the length of the longest chain.

Visual Representation

Pairs: [[1,2], [7,8], [4,5]] 1. Sort by end points: [1,2], [4,5], [7,8] 2. Chain: [1,2] -> [4,5] -> [7,8] Length: 3
Medium

Examples

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

Longest chain: [1,2] -> [3,4]. Note: [2,3] cannot follow [1,2] because 2 is not < 2.

Approach 1

Level I: Brute Force (Recursive Backtracking)

Intuition

Try all possible subsequences of pairs and check if they form a valid chain. To optimize slightly, we can first sort by start time and use recursion with a 'pick or skip' strategy.

Thought Process

  1. solve(idx, prevEnd)
  2. For each pair idx:
    • If pairs[idx].start > prevEnd, we can pick it: 1 + solve(idx + 1, pairs[idx].end).
    • We can always skip it: solve(idx + 1, prevEnd).
  3. Return the maximum of both.
⏱ O(2^N)💾 O(N)

Detailed Dry Run

pairs = [[1,2], [2,3], [3,4]]

  1. solve(0, -inf): Pick [1,2] -> solve(1, 2) -> Pick [3,4] -> SUCCESS (2 pairs)
  2. solve(0, -inf): Skip [1,2] -> solve(1, -inf) -> Pick [2,3] -> solve(2, 3) -> Pick [3,4] (FAIL: 3 not > 3)
java
public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        return solve(0, Integer.MIN_VALUE, pairs);
    }
    private int solve(int idx, int prevEnd, int[][] pairs) {
        if (idx == pairs.length) return 0;
        int taken = 0;
        if (pairs[idx][0] > prevEnd) taken = 1 + solve(idx + 1, pairs[idx][1], pairs);
        int notTaken = solve(idx + 1, prevEnd, pairs);
        return Math.max(taken, notTaken);
    }
}
Approach 2

Level II: Dynamic Programming (LIS Variation)

Intuition

This problem is perfectly analogous to Longest Increasing Subsequence (LIS). We want to find the longest chain where each pair follows the previous one.

Thought Process

  1. Sort the pairs by their start element.
  2. Initialize a dp array where dp[i] is the length of the longest chain ending at index i (initially all 1).
  3. For each i, check all j < i: if pairs[j].end < pairs[i].start, then dp[i] = max(dp[i], dp[j] + 1).

Pattern: Dynamic Programming / LIS

⏱ O(N^2)💾 O(N)

Detailed Dry Run

pairs = [[1,2], [2,3], [3,4]], dp=[1, 1, 1]

  1. i=1 ([2,3]): j=0 ([1,2]). 2 is not > 2. dp[1]=1.
  2. i=2 ([3,4]): j=0 ([1,2]). 3 > 2. dp[2]=max(1, dp[0]+1)=2.
  3. i=2 ([3,4]): j=1 ([2,3]). 3 is not > 3. dp[2]=2. Max dp = 2.
java
public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int n = pairs.length, max = 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; 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);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
Approach 3

Level III: Optimal Greedy (Interval Scheduling-Style)

Intuition

To fit the maximum number of intervals into a chain, we should always pick the pair that ends the earliest. This leaves the maximum room for subsequent pairs.

Thought Process

  1. Sort pairs by their end element pair[1].
  2. Maintain currEnd of the chain.
  3. For each pair, if its start > currEnd, add it to the chain and update currEnd.

Pattern: Interval Selection / Activity Selection

⏱ O(N log N) for sorting.💾 O(1) excluding sort space.

Detailed Dry Run

pairs = [[1,2], [7,8], [4,5]] Sorted by end: [[1,2], [4,5], [7,8]]

PaircurrEndAction
[1,2]2Pick [1,2], count=1
[4,5]54 > 2? YES. Pick [4,5], count=2
[7,8]87 > 5? YES. Pick [7,8], count=3
java
public class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        int count = 0, currEnd = Integer.MIN_VALUE;
        for (int[] p : pairs) {
            if (p[0] > currEnd) {
                count++;
                currEnd = p[1];
            }
        }
        return count;
    }
}
← Previous QuestionMinimum Number of Taps to Water Garden
Next Question →Meeting Rooms II