 Participate in Codex, Test Your Skills & Win BIG # Chain of Pairs

Problem Description

Given a `N * 2` array A where (A[i], A[i]) represents the ith pair.

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 , similarly in this way a chain of pairs can be formed.

Find the length of the longest chain subsequence which can be formed from a given set of pairs.

Problem Constraints

1 <= N <= 103

1 <= A[i] < A[i] <= 104

Input Format

First and only argument is an 2D integer array A of size `N * 2` representing the N pairs.

Output Format

Return a single integer denoting the length of longest chain subsequence of pairs possible under given constraint.

Example Input

Input 1:

``` A = [  [5, 24]
[39, 60]
[15, 28]
[27, 40]
[50, 90]
]
```

Input 2:

```
A = [   [10, 20]
[1, 2]
]
```

Example Output

Output 1:

``` 3
```

Output 2:

``` 1
```

Example Explanation

Explanation 1:

``` Longest chain that can be formed is of length 3, and the chain is [ [5, 24], [27, 40], [50, 90] ]
```

Explanation 2:

``` Longest chain that can be formed is of length 1, and the chain is [ [1, 2] ] or [ [10, 20] ]
```

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details. Hints
• Hint 1
• Solution Approach
• Complete Solution
Asked In:

Loading...