Maximizing Pair Chains: DP Algo for Finding the Longest Chain in C++

Hey, so today we are going to solve Leetcode - Maximum Length of Pair Chain

Problem Link- https://leetcode.com/problems/pair-chain

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 curr = INT_MIN, count = 0;

         for(auto p : pairs){
         if(p[0] > curr){
          curr = p[1]; 
          count++; 
          }
         }

         return count; 
     }

}

We start with the definition of the findLongestChain function that takes a 2D vector of integers as input.
We then sort the pairs based on the second element in each pair using a lambda function.
We initialize two integer variables: curr to INT_MIN and count to 0.
We then loop through each pair in the sorted pairs vector and check if the first element of the pair is greater than curr.
If the first element is greater than curr, we update curr to be the second element of the current pair, increment the count variable, and continue to the next pair.
Finally, we return the count variable as the result of the function.

Let's take an example
Consider the following input for the pairs vector:

pairs = [[1, 2], [3, 4], [2, 3], [5, 6], [4, 7], [6, 8]]

Step 1: Sorting the Pairs The pairs are sorted based on the second element in each pair. After sorting, the pairs vector becomes:

pairs = [[1, 2], [2, 3], [3, 4], [4, 7], [5, 6], [6, 8]]

Step 2: Initializing Variables We initialize curr as INT_MIN and count as 0.

curr = -2147483648 count = 0

Step 3: Loop through Pairs We iterate through each pair in the sorted pairs vector:

pair = [1, 2] Since 1 > -2147483648 (curr), we update curr to 2 and increment count to 1.
pair = [2, 3] Since 2 > 2 (curr), we do not update curr and continue to the next pair.
pair = [3, 4] Since 3 > 2 (curr), we do not update curr and continue to the next pair.
pair = [4, 7] Since 4 > 3 (curr), we update curr to 7 and increment count to 2.
pair = [5, 6] Since 5 > 7 (curr), we do not update curr and continue to the next pair.
pair = [6, 8] Since 6 > 7 (curr), we update curr to 8 and increment count to 3.

Step 4: Return the Result Finally, we return the value of count, which is 3 in this case. It represents the length of the longest chain of pairs where each pair's second element is less than the first element of the next pair in the chain.

So, the function findLongestChain returns 3 for the given input pairs vector.

DSA - Maximum Length of Pair Chain - C++,Dynamic Programming