You are actually very busy man. You have a big schedule of activities. Your aim is to do as much as activities as possible.

In the given figure, if you go to date with crush, you cannot participate in the coding contest and you can’t watch the movie. Also if you play DotA, you can’t study for the exam. If you study for the exam you can’t sleep peacefully. The maximum number of activities that you can do for this schedule is 3. 

Either you can

  • watch movie, play DotA and sleep peacefully (or)
  • date with crush, play DotA and sleep peacefully

Input Specifications

The first line consists of an integer T, the number of test cases. For each test case the first line consists of an integer N, the number of activities. Then the next N lines contains two integers m and n, the start and end time of each activity.

Output Specifications

For each test case find the maximum number of activities that you can do.

Input Constraints

1 <= T <=10
1 <= N <= 100000
0 <= start < end <= 1000000


Sample Input: (empty lines just for clarity)
3 9
2 8
6 9

1 7
5 8
7 8
1 8

7 9
0 10
4 5
8 9
4 10
5 7

Sample Output:

hide comments
sktibrewal: 2018-03-27 09:46:21

Activity Selection Problem

bani_raheja: 2018-03-13 19:24:56

dont even look at the graph given in the question. Its just there to explain the question and has nothing to do with the test cases. Confused me a lot

atu1_rana: 2018-01-03 07:33:33

Perfect schedule :D

madhugupta7979: 2017-12-05 08:23:38

I have used simple [spoiler] and BufferedReader for taking inputs....dont know why I'm getting TLE...Someone Please Help!

Last edit: 2018-01-09 20:55:16
sherlock11: 2017-10-20 14:24:38

this was a nice problem and it is "simple" ad-hoc..................................if u know what to do!!!!!!!!!!
do whatever but never miss u'r date

prateek_codec: 2017-10-15 14:02:42

Typical [spoiler]!!

Last edit: 2018-01-09 20:55:48
bloodseeker98: 2017-09-29 16:53:59

for java users try using faster input output techniques

pranjal_rai: 2017-09-28 19:27:09

AC in one go. simple adhoc, no stl required.

sonorous: 2017-09-27 20:31:01

AC in 3rd go!! STL :)

akashbhalotia: 2017-08-21 21:39:45

Hey admin, all Java submissions are getting TLE.

Added by:cegprakash
Time limit:0.324s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64