536. Get it Done
0
Medium
Aryan has a busy weekend ahead with a lot of pending tasks. He wants to complete as many tasks as possible, considering each task's start and end times. Once he starts a task, he cannot switch to another task until completing the current one. Your task is to assist Aryan in maximizing the number of tasks he can complete. Please note that there are multiple test cases in this problem.
Input Format
The first line of input contains an integer T, representing the number of test cases. For each test case, the first line contains an integer N, representing the number of activities. The next N lines contain two integers m and n, representing the start and end times of each activity.
Output Format
For each test case, output the maximum number of activities that can be completed.
Example
Input
3
3
3 9
2 8
6 9
4
1 7
5 8
7 8
1 8
6
7 9
0 10
4 5
8 9
4 10
5 7
Output
1
2
3
Constraints
1 <= T <=10
1 <= N <= 100000
0 <= start < end <= 1000000
1 <= N <= 100000
0 <= start < end <= 1000000
Loading...
View Submissions
Console