DAY 84 - 646. Maximum Length of Pair Chain

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

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:

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: