You are given N pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. You have to find the longest chain which can be formed from the given set of pairs.

For example, if the given pairs are {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, then the longest chain that can be formed is of length 3, and the chain is {{5, 24}, {27, 40}, {50, 90}}

lets use dynamic programming to solve this question:
c++ implementation:

t is the no.of test cases:
```// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

struct val{
int first;
int second;
};

int maxChainLen(struct val p[],int n);
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
val p[n];
for(int i=0;i<n;i++)
{
cin>>p[i].first>>p[i].second;
}

cout<<maxChainLen(p,n)<<endl;
}
return 0;
}// } Driver Code Ends

/*
The structure to use is as follows
struct val{
int first;
int second;
};*/

bool logic(struct val p, struct val q){
return p.first < q.first;
}
int maxChainLen(struct val p[],int n)
{

sort(p, p+n, logic);
int dp[n];

for(int i=0;i<n;i++)
dp[i]=1;

for(int i=1;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(p[i].first>p[j].second)
dp[i]=max(dp[i],dp[j]+1);
}
}
int maxele=dp;

for(int i=1;i<n;i++)
maxele=max(maxele,dp[i]);

return maxele;

}```

darkmode