Maximum Length of Pair Chain - Practice Coding Problems

Maximum Length of Pair Chain - Problem

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

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length of the longest chain which can be formed. You do not need to use up all the given intervals. You can select pairs in any order.

Input & Output

Example 1 — Basic Chain

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

› Output: 2

💡 Note: The longest chain is [1,2] → [3,4]. We can't use [2,3] because 2 is not less than 2.

Example 2 — All Can Chain

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

› Output: 3

💡 Note: After sorting by end time: [1,2] → [4,5] → [7,8]. All pairs can form a valid chain.

Example 3 — No Chaining Possible

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

› Output: 1

💡 Note: Cannot chain [1,4] → [2,3] because 4 ≥ 2. Maximum chain length is 1.

Constraints

n == pairs.length
1 ≤ n ≤ 1000
-1000 ≤ left_i < right_i ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Pairs

Array of [start, end] pairs that need to be chained

Chain Condition

Pair [a,b] can be followed by [c,d] if b < c

Find Maximum

Return the longest possible chain length

Key Takeaway

🎯 Key Insight: Greedy selection by earliest end time maximizes future chaining opportunities

Asked in

G Google 15 a Amazon 12 F Facebook 8

The key insight is that this is an activity selection problem. The greedy approach works optimally: sort pairs by end time and greedily select non-overlapping pairs. Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2ⁿ × n)	O(n)	Generate all possible subsequences and check which ones form valid chains
Dynamic Programming	O(n²)	O(n)	Sort pairs and use DP to find longest increasing subsequence of valid chains
Greedy - Activity Selection	O(n log n)	O(1)	Sort by end time and greedily select pairs that don't overlap

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all possible subsequences of pairs
Step 2: For each subsequence, check if it forms a valid chain
Step 3: Return the maximum length among valid chains

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate All Subsequences

Create every possible combination of pairs

Validate Each Chain

Check if pairs can form a valid chain

Find Maximum

Return the longest valid chain length

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int pairs[1000][2];
    int size;
} PairArray;

int isValidChain(int chain[][2], int size) {
    for (int i = 1; i < size; i++) {
        if (chain[i-1][1] >= chain[i][0]) {
            return 0;
        }
    }
    return 1;
}

int generateCombinations(int pairs[][2], int pairCount, int index, int current[][2], int currentSize) {
    if (index == pairCount) {
        if (isValidChain(current, currentSize)) {
            return currentSize;
        }
        return 0;
    }
    
    // Don't include current pair
    int maxLen = generateCombinations(pairs, pairCount, index + 1, current, currentSize);
    
    // Include current pair
    current[currentSize][0] = pairs[index][0];
    current[currentSize][1] = pairs[index][1];
    int newMax = generateCombinations(pairs, pairCount, index + 1, current, currentSize + 1);
    if (newMax > maxLen) maxLen = newMax;
    
    return maxLen;
}

int solution(int pairs[][2], int pairCount) {
    int current[1000][2];
    return generateCombinations(pairs, pairCount, 0, current, 0);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int pairs[1000][2];
    int pairCount = 0;
    
    // Simple parsing for [[a,b],[c,d]] format
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']' || *(ptr+1)) {
        if (*ptr == '[') {
            ptr++;
            pairs[pairCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            if (*ptr) ptr++;
            pairs[pairCount][1] = atoi(ptr);
            pairCount++;
            while (*ptr && *ptr != ']') ptr++;
        }
        if (*ptr) ptr++;
    }
    
    printf("%d\n", solution(pairs, pairCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2ⁿ possible subsequences, each takes O(n) time to validate

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth for generating combinations

⚡ Linearithmic Space

98.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler