> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/dp-+-binary-search/646.-maximum-length-of-pair-chain.md).

# 646. Maximum Length of Pair Chain

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: pairs = [[1,2],[2,3],[3,4]]
</strong><strong>Output: 2
</strong><strong>Explanation: The longest chain is [1,2] -> [3,4].
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: pairs = [[1,2],[7,8],[4,5]]
</strong><strong>Output: 3
</strong><strong>Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:
Sort and at end index, Not take/ Take
If take, using BS find the next just greater index and move along
```

### Links

<https://leetcode.com/problems/maximum-length-of-pair-chain/description/>

### Video Links

### Approach 1:

```
DP + BS
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<int>dp;
    int binary_search(vector<vector<int>>& pairs, int index, int val){
        int low=index;
        int high=pairs.size()-1;
        int ans=pairs.size();

        while(low<=high){
            int mid = low + (high-low)/2;
            // Mistake of not writing pairs[index/mid] and <= 
            if(pairs[mid][0] <= val)
                low = mid+1;

            else{
                ans = mid;
                high = mid-1;
            }
        }

        return ans;
    }

    int find_ans(vector<vector<int>>& pairs, int index){
        if(index >= pairs.size())
            return 0;

        if (dp[index] != -1)
            return dp[index];

        int not_take = find_ans(pairs, index+1);

        int next_index = binary_search(pairs, index+1, pairs[index][1]);
        
        int take = 1 + find_ans(pairs, next_index);

        return dp[index] = max(take, not_take);
    }

    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end());
        dp = vector<int> (pairs.size(),-1);
        return find_ans(pairs, 0);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###