## Similar Problems

Similar Problems not available

# Maximum Length Of Pair Chain - Leetcode Solution

## Companies:

LeetCode: Maximum Length Of Pair Chain Leetcode Solution

Difficulty: Medium

Topics: greedy dynamic-programming sorting array

Problem: You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

You have to find the length of the longest chain which can be formed from the given set of pairs.

Example: Input: [[1,2], [2,3], [3,4]] Output: 2 Explanation: The longest chain is [1,2] -> [3,4]

Solution: To solve the given problem, we need to follow the following steps:

- Sort the given pairs based on the second value of each pair.
- Iterate through the sorted pairs and keep a variable for the count of the maximum chain length. Initially, set it to 1.
- For each pair, check if the second value of the previous pair is less than the first value of the current pair. If yes, then increment the count of chain length and update the second value of the previous pair to the second value of the current pair.
- Return the count of chain length.

Pseudo Code:

```
def findLongestChain(pairs):
# Sort the pairs based on the second value
pairs.sort(key=lambda x: x[1])
# Set the maximum chain length to 1
max_length = 1
# Keep track of the second value of the previous pair
prev_second_value = pairs[0][1]
# Iterate through the pairs starting from the second pair
for i in range(1, len(pairs)):
# If the second value of the previous pair is less than the first value of the current pair
if prev_second_value < pairs[i][0]:
# Update the maximum chain length and the second value of the previous pair
max_length += 1
prev_second_value = pairs[i][1]
# Return the maximum chain length
return max_length
```

Time Complexity:
Sorting the pairs takes O(n*logn) time. Iterating through the pairs and updating the count of chain length takes O(n) time. Hence, the overall time complexity of the algorithm is O(n*logn).

Space Complexity: We are not using any extra space in the algorithm except for the variables used for storing the count of chain length and the second value of the previous pair. Hence, the space complexity of the algorithm is O(1).

## Maximum Length Of Pair Chain Solution Code

`1`