DAY 84 - 646. Maximum Length of Pair Chain
Tags: leetcode, beginners, algorithms, codenewbie
Published: 2023-08-26 17:22:51

Hey Guys!, Welcome to day 84. Today we are going to solve today's daily leetcode problem. So let's get right into it.

---

## Question: [646. Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/description/)

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.

---

### Examples:

**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].

---

### Intuition: Greedy Approach

The greedy approach is based on the idea of selecting pairs in a way that maximizes the length of the valid chain. The goal is to find a sequence of pairs where each pair (a, b) is followed by a pair (c, d) such that b < c. The key insight is to sort the pairs in ascending order based on the second element b. This sorting ensures that pairs with smaller b values are placed earlier in the sequence, making it more likely to find valid chains.

**Algorithm:**

1. Define a custom comparison function named `compSort` that compares two pairs based on the second element (`b`) of each pair.
2. Sort the given list of pairs in ascending order using the `compSort` comparison function.
3. Initialize a variable `cur` to store the current ending value of the chain. Set it initially to a very small value (`INT_MIN`).
4. Initialize a variable `count` to keep track of the length of the longest chain. Set it initially to 0.
5. Iterate through each pair in the sorted list:
   - If the current pair's first element `a` is greater than the current ending value `cur`, update `cur` to the second element `b` of the current pair, and increment the `count`.
   - If the condition is not met, move on to the next pair without updating `cur`.
6. Return the final value of `count`, which represents the length of the longest chain of pairs.

---

**Code:**


```cpp
class Solution {
public:
    int helper(int index, int prev, vector<vector<int>>& pairs, vector<vector<int>>&dp){
        if(index == pairs.size()) return 0;

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

        int pick = -1e9;
        int notPick = helper(index+1,prev,pairs,dp);
        if(prev == -1 || pairs[prev][1] < pairs[index][0]){
            pick = 1 + helper(index+1,index,pairs,dp);
        }

        return dp[index][prev+1] = max(pick,notPick);
    }
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(),pairs.end());

        vector<vector<int>> dp(pairs.size(),vector<int>(pairs.size()+1,-1));

        return helper(0,-1,pairs,dp);
    }
};

```

---

### Complexity Analysis:

| Complexity | Analysis |
|------------|----------|
| Time       | O(n * log n)|
| Space      | O(1) |