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

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

hide comments
2023-08-19 14:19:41 SUHAS E J
strange c++ compiler spoj has. if I write a <= b in the compare fn of sort, i get SIGSEGV, but if I use a < b, then solution is accepted. Wasted a couple of hours on this nonsense.

Reply: That's the way comparator is supposed to work in any programming language. You've to implement a<b and not a<=b.

Last edit: 2023-09-08 16:09:54
2021-12-31 22:02:13
69th
2021-06-26 08:16:00
did the man only play dota for 2 games? disgrace...

Reply: Check the image.. 3 hours is enough to play 4-5 games of DotA

Last edit: 2023-09-08 16:11:18
2021-06-13 09:41:43
Why [misleading_spoiler] solution does not work ?

Last edit: 2023-09-08 16:11:53
2021-01-06 20:54:21
@jeet9
nothing special for using py
I just used the fast I/O from PyRival template.....remaining is pretty standard
2020-11-03 04:42:45
getting runtime error (SIGSEGV).
2020-11-01 10:50:09
u can do even with structures


Last edit: 2020-11-01 10:50:19
2020-08-22 12:34:30
AC in one GO!!
2020-08-22 12:25:22
@goblin69 u had to check >= not only greater
2020-08-22 10:11:27
yes vector pair helped me in my case too..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.