<p>You are given an array of <code>n</code> pairs <code>pairs</code> where <code>pairs[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> and <code>left<sub>i</sub> &lt; right<sub>i</sub></code>.</p>

<p>A pair <code>p2 = [c, d]</code> <strong>follows</strong> a pair <code>p1 = [a, b]</code> if <code>b &lt; c</code>. A <strong>chain</strong> of pairs can be formed in this fashion.</p>

<p>Return <em>the length longest chain which can be formed</em>.</p>

<p>You do not need to use up all the given intervals. You can select pairs in any order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == pairs.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>-1000 &lt;= left<sub>i</sub> &lt; right<sub>i</sub> &lt;= 1000</code></li>
</ul>

bool comparator(vector<int> a, vector<int> b)
{
    return a[0]<b[0];
}

bool comparator2(vector<int> a, vector<int> b)
{
    return a[1]<b[1];
}

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end(), comparator2);
        int maxlen = 1; 
        int curr = pairs[0][1];
        for(int i = 1 ; i< n; i++)
        {
            if (curr < pairs[i][0])
            {
                curr = pairs[i][1];
                maxlen++;
            }
        }

        return maxlen;
    }

    int sol1findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), comparator);
        vector<int> dp(pairs.size(), -1);
        int maxlen = INT_MIN; 
        for(int i = 0 ; i< dp.size(); i++)
        {
            maxlen = max(helper( pairs, dp, i), maxlen);
        }

        //  for( int i = 0; i < pairs.size(); i++)
        // {
        //     cout<<pairs[i][0]<<"<->"<<pairs[i][1]<<"<->"<<dp[i]<<"      ";
        // }
        // cout<<endl;

         return maxlen;
    }

    int helper(vector<vector<int>>& pairs, vector<int>& dp, int ind)
    {
        int n = pairs.size();
        if ( ind>= n)
            return 0;
        
        if ( dp[ind] != -1)
            return dp[ind];
        
        int maxlen  = 1;
        for ( int i = ind+1; i<n; i++)
        {
            if (pairs[ind][1]< pairs[i][0])
                maxlen = max(1+helper(pairs, dp, i), maxlen);
        }
        dp[ind] = maxlen;
        return maxlen;
    }
};
57804