algoadvance

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

A pair (c, d) can follow another pair (a, b) if and only if b < c. A chain of pairs can be formed in this fashion.

Return the length of the longest chain which can be formed.

Example

Example 1:

Example 2:

Clarifying Questions

  1. Are all pairs guaranteed to have left_i < right_i?
    • Yes, the problem statement guarantees it.
  2. Can pairs have duplicate elements?
    • The problem does not specify, so we assume it is possible.
  3. What is the expected time complexity?
    • Typically problems related to dynamic programming or greedy algorithms aim for O(n^2) or O(n log n) complexities.

Strategy

To solve this problem, we can use a greedy algorithm. Here’s the strategy:

  1. Sort Pairs by Ending Element: This helps to always consider the earliest possible end for chaining which maximizes the chance of forming a longer chain.
  2. Iterate and Form the Chain:
    • Initialize cur_end to negative infinity and chain_length to 0.
    • Iterate through the pairs.
    • If the current pair can follow the last picked pair (i.e., current pair’s start is greater than cur_end), update cur_end to the end of the current pair and increment the chain length.

This ensures that we are always trying to extend the chain with the earliest possible end, making our solution both optimal and efficient.

Code

def findLongestChain(pairs):
    # Sort pairs by their ending element
    pairs.sort(key=lambda x: x[1])
    
    cur_end = float('-inf')
    chain_length = 0
    
    for pair in pairs:
        if cur_end < pair[0]:
            cur_end = pair[1]
            chain_length += 1
            
    return chain_length

# Test cases
print(findLongestChain([[1,2], [2,3], [3,4]]))  # Output: 2
print(findLongestChain([[1,2], [7,8], [4,5]]))  # Output: 3

Time Complexity

Therefore, the overall time complexity is O(n log n), which is quite efficient for this problem.

This approach ensures that we can efficiently determine the maximum length of a chain that can be formed using the given pairs.

Try our interview co-pilot at AlgoAdvance.com