Max length chain

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. Your task is to complete the function maxChainLen which returns an integer denoting the longest chain which can be formed from a given set of pairs.

Input:
The first line of input contains an integer T denoting the no of test cases then T test cases follow .Then T test cases follow . The first line of input contains an integer N denoting the no of pairs . In the next line are 2*N space separated values denoting N pairs.

Output:
For each test case output will be the length of the longest chain formed.

Constraints:

1<=T<=100
1<=N<=100

Example (To be used only for expected output):

Input

2
5
5  24 39 60 15 28 27 40 50 90
2
5 10 1 11 

Output

3
1
​

Explanation

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

(ii) The max length chain possible is only of length one.

Code:

int maxChainLen(struct val p[],int n)
{
int dp[n];
dp[0]=1;
for(int i=1;i<=n;i++) {
    dp[i]=1;
   for(int j=0;j<i;j++) {
       if(p[j].second < p[i].first && dp[i]<dp[j]+1) {
           dp[i]=dp[j]+1;
       }
   }
}

int max=dp[0];
for(int i=0;i<n;i++) {
    if(dp[i]>max) {
        max=dp[i];
    }
}
return max;
}

Algorithm:
Same as Longest Increasing Subsequnce except condition is changed((p[j].second < p[i].first)

But on submission, some test cases are failing; Where is this algorithm going wrong ?

Below test case is failing:

34
778 887 794 916 336 387 493 650 363 422 28 691 60 764 541 927 173 427 212 737 369 568 430 783 531 863 68 124 136 930 23 803 59 70 168 394 12 457 43 230 374 422 785 920 199 538 316 325 371 414 92 527 957 981 863 874 171 997 282 306 85 926 328 337 506 847 314 730

Its Correct output is:
8

And Your Code's output is:
4

If you consider each pair as an interval on the real line then the challenge is to find the Maximum Disjoint Set (MDS) of intervals. There's a fairly well known greedy algorithm that finds the MDS in O(nLgn).

The key is to first order the pairs by their end point. Most explanations of the algorithm then talk about removing overlapping intervals from the set, but that's not really necessary. Instead you can just walk through the sorted list and only increment the current pair if you find one that's disjoint.

L = list of n pairs (a, b), a < b, sorted by b
count = 1
curr = 0
for i = 1 to n-1
  if L(i).a > L(curr).b
    count = count + 1
    curr = i

The result is then given by count