AKVISM03 - Kyle Makes a List
Kyle got "N" pairs (Ai, Bi) such that 0 <= i < N and Ai < Bi. He wants to make a list out of these "N" pairs. But there is a limitation on it, If (x, y) comes after (a, b) in the list, then x must be greater than b.
For example:
- (1, 3), (5, 8), (13, 15) is a valid list.
- (1, 3), (2, 4), (5, 8) is not a valid list.
Your task is to form the longest list that is possible using the "N" pairs.
Input
First line will contain "N", the number of pairs Kyle has. Each of the next "N" lines will contain two integers Ai and Bi.
Output
Output a single integer, length of the longest list it is possible to make using these pairs.
Constraints
1 <= N <= 1000
0 <= Ai < Bi <= 109
Example
Input: 5 4 8 1 2 2 8 13 20 7 14 Output: 3
Explanation
Longest possible list is (1, 2), (4, 8) and (13, 20).
Added by: | Ankit Kumar Vats |
Date: | 2013-07-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Self |