We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Length of Pair Chain

Number: 646

Difficulty: Medium

Paid? No

Companies: Google, Apple, Amazon, Bloomberg, Adobe

Problem Description

Given an array of pairs where each pair is represented as [left, right] with left < right, determine the length of the longest chain that can be formed. A chain can be built by connecting pairs such that for two consecutive pairs [a, b] and [c, d], b < c. You may select the pairs in any order, and not all pairs must be used.

Key Insights

  • Sort the pairs based on their second (right) element to make a greedy selection.
  • The greedy approach ensures that by choosing the pair with the smallest end, you leave maximum space for subsequent pairs.
  • After sorting, iterate through the list and select a pair if its start is greater than the end value of the last selected pair.
  • This strategy results in the optimal solution.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) if we ignore the space used to store the input.

Solution

The solution involves sorting the pairs by their right endpoints. Start with a variable to keep track of the current end of the chain (initialized to negative infinity) and a counter for the chain length. Iterate over the sorted pairs; if the current pair's start is greater than the current end, it can be added to the chain. Update the counter and the current end accordingly. This greedy method ensures the longest possible chain is built by always choosing the next available pair that leaves room for as many subsequent pairs as possible.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java.

# Function to compute the maximum length of a pair chain
def findLongestChain(pairs):
    # Sort pairs based on their second element (end value)
    pairs.sort(key=lambda x: x[1])
    
    # Initialize the number of pairs in the longest chain and the current end marker
    chain_length = 0
    current_end = float('-inf')
    
    # Iterate over each pair in the sorted array
    for pair in pairs:
        # If the current pair's start is greater than the current end, it can be added to the chain
        if pair[0] > current_end:
            chain_length += 1
            current_end = pair[1]  # Update the current end to the end of the current pair
            
    return chain_length

# Example usage:
pairs = [[1,2], [7,8], [4,5]]
print(findLongestChain(pairs))  # Expected Output: 3
← Back to All Questions