Problem Description

You are given an array of n pairs where each pair is represented as pairs[i] = [left_i, right_i] with the constraint that left_i < right_i.

A pair p2 = [c, d] can follow another pair p1 = [a, b] if and only if b < c. In other words, the second element of the first pair must be less than the first element of the second pair for them to form a valid sequence.

A chain is a sequence of pairs where each pair follows the previous one according to the rule above. For example, if we have pairs [1, 2], [3, 4], and [5, 6], they can form a chain because 2 < 3 and 4 < 5.

Your task is to find the maximum length of a chain that can be formed from the given pairs. You can:

• Select any subset of the given pairs (you don't need to use all of them)
• Arrange the selected pairs in any order to form the longest possible chain

The solution uses a greedy approach: after sorting the pairs by their ending values (second element), it iterates through them and selects a pair whenever it can legally follow the previously selected pair. The variable pre tracks the ending value of the last selected pair, and ans counts the total number of pairs in the chain. A pair [a, b] is added to the chain if its starting value a is greater than pre, ensuring no overlap between consecutive pairs in the chain.

Intuition

The key insight is recognizing that this problem is similar to the classic "Activity Selection Problem" or "Interval Scheduling Problem". When we want to select the maximum number of non-overlapping intervals, we should be greedy about which intervals to choose.

Think about it this way: if we have already selected some pairs to form a chain, and we want to add the next pair, we want to leave as much "room" as possible for future pairs. This means we should prefer pairs that end earlier, because they give us more opportunities to add subsequent pairs.

For example, suppose we have pairs [1, 100] and [1, 2]. If we choose [1, 100] first, we can only add pairs that start after 100, which severely limits our options. But if we choose [1, 2] first, we can add any pair that starts after 2, giving us many more possibilities.

This leads us to the greedy strategy:

1. Sort all pairs by their ending values (second element)
2. Always pick the pair with the earliest ending that can legally follow our current chain

Why does sorting by the ending value work? Because once we process pairs in this order, we know that when we select a pair, we're making the locally optimal choice - we're picking the pair that ends earliest among all valid options, thus maximizing the "space" available for future selections.

The algorithm maintains pre as the ending point of our current chain. For each new pair [a, b], if a > pre (meaning this pair can follow our chain), we greedily add it and update pre = b. This greedy choice at each step leads to the globally optimal solution - the longest possible chain.

Learn more about Greedy, Dynamic Programming and Sorting patterns.

Solution Approach

The implementation follows a sorting + greedy strategy to build the longest chain efficiently.

Step 1: Sort the pairs

pairs.sort(key=lambda x: x[1])

We sort all pairs in ascending order by their second element (ending value). This ensures that when we process pairs sequentially, we always consider pairs that end earlier first, which aligns with our greedy strategy.

Step 2: Initialize tracking variables

ans, pre = 0, -inf

• ans: Counts the number of pairs in our chain (initially 0)
• pre: Tracks the ending value of the last selected pair (initialized to negative infinity to ensure the first pair can always be selected)

Step 3: Greedily build the chain

for a, b in pairs:
    if pre < a:
        ans += 1
        pre = b

We iterate through the sorted pairs. For each pair [a, b]:

• Check if this pair can follow the current chain: pre < a (the ending of the last selected pair must be less than the starting of the current pair)
• If yes, we add this pair to our chain:
  • Increment ans by 1 (we've added one more pair to the chain)
  • Update pre = b (the new ending point of our chain is b)
• If no, we skip this pair and continue to the next one

Step 4: Return the result

return ans

After processing all pairs, ans contains the maximum length of the chain we can form.

Time Complexity: O(n log n) where n is the number of pairs, dominated by the sorting step.

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (typically O(log n) for the recursion stack in quicksort).

The beauty of this approach is that by sorting first and then making greedy choices, we ensure that we never need to backtrack or reconsider our decisions - each local optimal choice leads to the global optimum.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the greedy approach works.

Given pairs: [[1,2], [7,8], [4,5], [2,3]]

Step 1: Sort by ending values (second element) After sorting: [[1,2], [2,3], [4,5], [7,8]]

Step 2: Initialize variables

• ans = 0 (no pairs in chain yet)
• pre = -infinity (allows first pair to be selected)

Step 3: Process each pair greedily

Iteration 1: Consider [1,2]

• Check: Is pre < 1? Yes, -infinity < 1
• Select this pair!
• Update: ans = 1, pre = 2
• Current chain: [[1,2]]

Iteration 2: Consider [2,3]

• Check: Is pre < 2? No, 2 is not < 2
• Skip this pair (it would overlap with our chain)
• No updates
• Current chain: [[1,2]]

Iteration 3: Consider [4,5]

• Check: Is pre < 4? Yes, 2 < 4
• Select this pair!
• Update: ans = 2, pre = 5
• Current chain: [[1,2], [4,5]]

Iteration 4: Consider [7,8]

• Check: Is pre < 7? Yes, 5 < 7
• Select this pair!
• Update: ans = 3, pre = 8
• Current chain: [[1,2], [4,5], [7,8]]

Step 4: Return result Maximum chain length = 3

The final chain is [1,2] → [4,5] → [7,8], where each pair follows the previous one (2 < 4 and 5 < 7). Notice how we skipped [2,3] because selecting it would have blocked us from choosing [4,5] later, resulting in a shorter chain. This demonstrates why the greedy approach of always choosing the pair with the earliest ending value works - it leaves maximum room for future selections.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation pairs.sort(key=lambda x: x[1]), which sorts the pairs based on their second element (ending value). Python's built-in sort function uses Timsort algorithm, which has a time complexity of O(n × log n) where n is the number of pairs. After sorting, there is a single linear pass through the sorted pairs with O(n) time complexity. Therefore, the overall time complexity is O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's Timsort requires O(log n) space for its recursive calls in the worst case. The algorithm itself only uses a constant amount of extra space for variables ans and pre, which is O(1). Therefore, the overall space complexity is O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Sorting by the Wrong Element

The Mistake: A natural instinct might be to sort by the first element (starting value) instead of the second element (ending value):

# WRONG approach
pairs.sort(key=lambda x: x[0])  # Sorting by first element

Why It Fails: Consider pairs: [[1, 100], [2, 3], [4, 5]]

• Sorting by first element gives: [[1, 100], [2, 3], [4, 5]]
• The greedy algorithm would select [1, 100] first, preventing us from selecting [2, 3] and [4, 5]
• Maximum chain length achieved: 1

The Correct Approach:

# CORRECT approach
pairs.sort(key=lambda x: x[1])  # Sorting by second element

With the same pairs sorted by ending value: [[2, 3], [4, 5], [1, 100]]

• We can select [2, 3] then [4, 5], giving us a chain length of 2

Pitfall 2: Confusing Chain Rules with Interval Merging

The Mistake: Treating this as an interval merging problem where touching intervals are allowed:

# WRONG - allowing pairs to touch
for start, end in pairs:
    if previous_end <= start:  # Using <= instead of <
        chain_length += 1
        previous_end = end

Why It Fails: The problem explicitly states that for pair p2 = [c, d] to follow p1 = [a, b], we need b < c (strictly less than), not b <= c.

Example: [[1, 2], [2, 3]]

• With <=: Both pairs would be selected (incorrect - they touch at point 2)
• With <: Only one pair can be selected (correct - no valid chain exists)

Pitfall 3: Attempting Dynamic Programming When Greedy Suffices

The Mistake: Over-engineering with dynamic programming:

# Unnecessarily complex DP approach
def findLongestChain(pairs):
    n = len(pairs)
    pairs.sort()
    dp = [1] * n
  
    for i in range(1, n):
        for j in range(i):
            if pairs[j][1] < pairs[i][0]:
                dp[i] = max(dp[i], dp[j] + 1)
  
    return max(dp)

Why It's Inefficient:

• Time complexity: O(n²) vs O(n log n) for the greedy approach
• Space complexity: O(n) vs O(1) for the greedy approach
• The greedy solution is both simpler and more efficient

The Better Solution: Stick with the greedy approach after sorting by ending values - it's optimal and more efficient.