BUSYMAN - I AM VERY BUSY


I AM VERY BUSY

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

Example

Sample Input: (empty lines just for clarity)
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

Sample Output:
1
2
3

hide comments
harry_shit: 2019-11-11 17:55:04

ezypzy

hemant1612: 2019-10-25 06:29:40

[5p01L34]

Last edit: 2019-10-25 06:50:49
suraj1198: 2019-10-21 21:36:28

AC in one go..

emtiaz_001: 2019-09-06 12:37:55

just try to think about the finish and start time. cost me one wrong ans

aryan_007coder: 2019-08-12 10:24:48

i m using multimap and iterating in the loop till end but getting no output ....
plz help me out , i get no output most of the time using iteartor or multimap , what is the reason behind that??

bizan_007: 2019-08-11 10:21:44

AC in one go !!
try using [spoiler that won't help you] , things are even further simpler with its use , just a [spoiler] and ur done . Happy Coding ;)

Last edit: 2019-09-30 14:43:51
importme: 2019-07-25 12:37:49

[spoiler] implementation question

Last edit: 2019-09-30 14:46:43
sanket17: 2019-07-12 11:07:43

USE VECTOR<PAIR>

aryan29: 2019-06-01 14:28:53

AC in one go
Used [spoiler], vectors, pairs

Last edit: 2019-06-20 12:39:38
levinlmkwong: 2019-04-29 05:08:08

TLE using Python 3, sadness about Python :(
Switched to Python 2 with pypy and ACed, luckily don't need to implement it in C++


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