30. Maximum Length of Pair Chain

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:

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

Solution: (DP)

Approach: Sort the values on first column use dp to find maximum

class Solution
{
public:
    
    int findLongestChain(vector<vector<int>> &pairs)
    {
        sort(pairs.begin(), pairs.end());

        int n = pairs.size();
        vector<int> dp(n, 0);

        for (int i = 0; i < n; i++)
        {

            for (int j = 0; j < n; j++)
            {

                if (pairs[i][1] < pairs[j][0])
                {
                    dp[j] = max(dp[j], dp[i] + 1);
                }
            }
        }
        
        int mx = 0;
        for (int i = 0; i < n; i++)
        {
            if (dp[i] > mx)
            {
                mx = dp[i];
            }
        }

        return mx + 1;
    }
};

Time Complexity: O(n^2)