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
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++

ujjwalmittal: 2019-03-02 10:35:52

i do ont know why i am getting runtime error (sigsegv) besides the code achieving output in online compiler of c++ 14

shankygupta79: 2019-02-15 12:40:55

[spoiler] :-)

Last edit: 2019-03-11 23:40:20
sajalagrawal14: 2019-01-15 19:50:36

nice question
AC in one go
@ayushgupta1997 haha

Last edit: 2019-01-15 19:51:39
ayushgupta1997: 2018-12-28 12:27:55

Prefer sleeping than dating a crush lol :\

sohamkar76: 2018-08-30 16:14:55

I'm getting a WA and I'm not sure why? It seems to be working fine when I type in the above test case(without the empty lines of course). Any help would be much appreciated.

Last edit: 2018-08-30 16:15:26
masterchef2209: 2018-08-28 13:43:31

it is not as simple as it looks if you are first time encountering such problem, costed 2 WA before AC :(

Last edit: 2018-08-28 13:44:28
vaishcr7: 2018-08-27 20:23:16

Last edit: 2018-08-27 20:23:30
jeet9: 2018-08-05 22:06:47

Got AC.. But most importantly learnt the problem with Python. The same implementation in Python using the library function took >28M memory and got TLE.
Whereas C++ glided through the test cases like knife through the butter.
If anyone can get AC with Python please let me know. I am interested to learn about your approach. :)

crack_coder: 2018-08-02 02:54:04

Can anyone help me, I'm getting TLE error. https://ideone.com/eGxOs9

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