# Maximum Length of Pair Chain
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-length-of-pair-chain)
Canonical: https://scaleengineer.com/dsa/problems/maximum-length-of-pair-chain
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## Problem
You are given an array of `n` pairs `pairs` where `pairs[i] = [lefti, righti]` and `lefti < righti`.

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 longest chain which can be formed_.

You do not need to use up all the given intervals. You can select pairs in any order.

**Example 1:**

**Input:** pairs = [[1,2],[2,3],[3,4]]
**Output:** 2
**Explanation:** The longest chain is [1,2] -> [3,4].

**Example 2:**

**Input:** pairs = [[1,2],[7,8],[4,5]]
**Output:** 3
**Explanation:** The longest chain is [1,2] -> [4,5] -> [7,8].

**Constraints:**

* `n == pairs.length`
* `1 <= n <= 1000`
* `-1000 <= lefti < righti <= 1000`

# Approaches
## Dynamic Programming (LIS-based)
This approach models the problem as a variation of the classic Longest Increasing Subsequence (LIS) problem. The fundamental idea is to build the solution incrementally. We first sort the pairs by their starting points. Then, we use a dynamic programming array, `dp`, where `dp[i]` represents the length of the longest chain that can be formed ending with the `i`-th pair.
**Time:** `O(N^2)`. Sorting takes `O(N log N)`, but the nested loops for the DP calculation take `O(N^2)`, which dominates the overall complexity. · **Space:** `O(N)` to store the `dp` array.
**Pros:** Relatively straightforward to understand if you are familiar with the Longest Increasing Subsequence pattern.; Guaranteed to find the optimal solution.
**Cons:** The `O(N^2)` time complexity is less efficient than the greedy approach and may be too slow for larger constraints (though it passes for N <= 1000).
### Explanation
First, we sort the `pairs` array based on the first element of each pair. This ordering helps in building the chain, as we only need to consider previous pairs (`j < i`) to extend a chain ending at `pairs[i]`. 

We initialize a `dp` array of size `n` with all values set to 1. This is because any single pair constitutes a valid chain of length 1.

We then iterate through the sorted pairs from the second pair (`i = 1`) to the last. For each `pairs[i]`, we look back at all preceding pairs `pairs[j]` (where `j < i`). If we find a `pairs[j]` such that `pairs[j][1] < pairs[i][0]`, it means `pairs[i]` can follow `pairs[j]` to form a longer chain. We update `dp[i]` to be the maximum of its current value and `1 + dp[j]`. 

After iterating through all pairs, the longest chain could end at any position `i`. Therefore, the final answer is the maximum value found in the `dp` array.

```java
import java.util.Arrays;

class Solution {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) {
            return 0;
        }
        // Sort pairs based on the first element
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
        
        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        int maxChainLength = 1;
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // Check if pair i can follow pair j
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }
            maxChainLength = Math.max(maxChainLength, dp[i]);
        }
        
        return maxChainLength;
    }
}
```
### Algorithm
- Sort the `pairs` array based on the first element of each pair (`left_i`).
- Create a `dp` array of size `n` (where `n` is the number of pairs) and initialize all its elements to 1.
- Initialize a variable `maxChainLength` to 1.
- Iterate through the sorted pairs from `i = 1` to `n-1`:
  - For each `pairs[i]`, iterate through all previous pairs `j` from `0` to `i-1`:
    - If `pairs[j][1] < pairs[i][0]`, it means `pairs[i]` can follow `pairs[j]`.
    - Update `dp[i]` with the maximum of its current value and `1 + dp[j]`, i.e., `dp[i] = Math.max(dp[i], 1 + dp[j])`.
  - After the inner loop, update `maxChainLength = Math.max(maxChainLength, dp[i])`.
- Return `maxChainLength`.

## Greedy Approach by Sorting End Points
A more optimal solution can be achieved using a greedy algorithm. This approach is analogous to the classic Activity Selection Problem. The key insight is to always choose the pair that finishes the earliest. By doing so, we maximize the remaining "space" for subsequent pairs, which intuitively leads to the longest possible chain.
**Time:** `O(N log N)`. The dominant operation is sorting the array. The subsequent loop is a single pass, taking `O(N)` time. · **Space:** `O(log N)` to `O(N)`. This is the space required by the sorting algorithm. In Java, `Arrays.sort` for objects uses Timsort, which may require `O(N)` space in the worst case.
**Pros:** Highly efficient with `O(N log N)` time complexity.; Simple and concise implementation.; Uses constant extra space, apart from the space used for sorting.
**Cons:** The correctness of the greedy choice (sorting by end time) is not immediately obvious and relies on a proof similar to that for the Activity Selection Problem.
### Explanation
The first step is to sort the `pairs` array based on their end points (`right_i`) in ascending order. This is the crucial greedy choice. The pair that finishes first is `pairs[0]` after sorting.

We initialize our chain with this first pair. We set the `chainLength` to 1 and record the end point of this pair, `currentEnd = pairs[0][1]`.

Then, we iterate through the rest of the sorted pairs, from `i = 1` to `n-1`. For each `pairs[i]`, we check if it can follow the last pair in our current chain. The condition is `pairs[i][0] > currentEnd`.

If the condition is met, it means we can add `pairs[i]` to our chain. We increment `chainLength` and update `currentEnd` to the end point of this new pair, `pairs[i][1]`. Since the pairs are sorted by their end points, this new `currentEnd` is the earliest possible end time for a chain of this new length, which is the essence of the greedy strategy.

If the condition is not met, we simply skip `pairs[i]` and move to the next one, as including it would break the chain.

After iterating through all pairs, `chainLength` will hold the length of the longest possible chain.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) {
            return 0;
        }
        
        // Sort pairs based on the second element (end point)
        Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
        
        int chainLength = 1;
        int currentEnd = pairs[0][1];
        
        for (int i = 1; i < pairs.length; i++) {
            if (pairs[i][0] > currentEnd) {
                chainLength++;
                currentEnd = pairs[i][1];
            }
        }
        
        return chainLength;
    }
}
```
### Algorithm
- Sort the `pairs` array in ascending order based on the second element (`right_i`) of each pair.
- If the array is empty, return 0.
- Initialize `chainLength = 1` and `currentEnd = pairs[0][1]` (the end point of the first pair in the sorted list).
- Iterate through the sorted `pairs` array from the second element (`i = 1` to `n-1`).
- For each `pair[i]`, if its start point is greater than the end of the current chain (`pair[i][0] > currentEnd`):
  - This pair can extend the current chain, so increment `chainLength`.
  - Update `currentEnd` to the end point of this new pair, `currentEnd = pair[i][1]`.
- Return `chainLength`.

# Solutions
### Java

```java
class Solution {
public
  int findLongestChain(int[][] pairs) {
    Arrays.sort(pairs, Comparator.comparingInt(a->a[1]));
    int ans = 0;
    int cur = Integer.MIN_VALUE;
    for (int[] p : pairs) {
      if (cur < p[0]) {
        cur = p[1];
        ++ans;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int: ans, cur = 0, - inf for a, b in sorted(pairs, key=lambda x: x[1]): if cur < a: cur = b ans += 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int findLongestChain(vector<vector<int>> &pairs) {
    sort(pairs.begin(), pairs.end(),
         [](vector<int> &a, vector<int> b) { return a[1] < b[1]; });
    int ans = 0, cur = INT_MIN;
    for (auto &p : pairs) {
      if (cur < p[0]) {
        cur = p[1];
        ++ans;
      }
    }
    return ans;
  }
};

```