BYTESE2 - The Great Ball
Hogwarts has organized The Great Ball to welcome the schools participating in the Triwizard Tournament. The ball is being held in the Great Hall and The Weird Sisters have been called to play the band. The students drift in to dance and then go out when they get tired. Hagrid is stationed at the gate and is noting down the time at which people enter and leave the hall. At the end of the day, he wonders what the maximum number of dancers was during the course of the ball.
For convenience, he writes down for each person entering, the number of minutes from the start of the ball at which the person entered and left. The door of the hall is narrow, so at any time, either one person can enter or one person can exit, but not both.
For example, suppose the observations noted down by Hagrid are the following:
| Serial Number | Enters at | Leaves at |
| 1 | 1 | 7 |
| 2 | 2 | 4 |
| 3 | 6 | 9 |
| 4 | 3 | 8 |
| 5 | 5 | 10 |
Each line denotes the entry time and exit time of one person. (The identity of the person is not important - the same person may enter and leave many times. For instance, in the example, it might well be that the entries and exits recorded at serial number 2 and 5 refer to the same person).
In this example, the maximum size of the dancers during the ball was 4. This was achieved between time 6 and 7. Hagrid is not good at Math so he requires your help. Your task is to read the list of entry and exit times and compute the maximum number of dancers during the ball.
Input
The first line is a single integer, T (1<=T<=100), which is the number of test cases. For each of the test case, the first line contains a single integer N, (1<=N<=100), the number of entries and exits recorded. This is followed by N lines. Each of these lines consists of two integers, separated by a space, describing the entry and exit time of that person. The entry and exit times are guaranteed to be distinct, and the entry time will be less than the exit time. The constraint on entry and exit times is 10000000.
Output
A total of T lines each of them containing a single integer, denoting the maximum number of dancers during the ball.
Example
Input: 1 5 1 7 2 4 6 9 3 8 5 10 Output: 4
hide comments
|
ankit1cool:
2018-06-13 13:16:48
Easy using two pointer Last edit: 2018-06-13 16:24:29 |
|
vib_s02:
2018-05-27 11:16:45
used map.. |
|
karthik_vg:
2018-03-11 15:39:28
finally found my flaw in algol :D |
|
optimus_v2:
2018-01-10 18:40:21
Solved using Segment tree and Swipe line technique |
|
saurav52:
2017-08-21 22:13:23
used priority queue
|
|
anurag_333:
2017-07-22 05:17:29
n logn...........make pair of entry time with "L" and exit time with "r"...and sort the vector of pair.......when a "L" comes increment the counter and when a "r" comes decrement the counter...the max value of counter is the answer;
|
|
anubhav1772:
2017-07-20 16:28:42
AC in one GO :)
|
|
|
anurag_333:
2017-07-19 12:10:11
cant use prefix array since n is small and time interval is large........for greater n prefix array is good
|
|
rohit9934:
2017-06-16 13:35:29
Easy with two pointer technique. |
|
starbot:
2017-06-15 18:53:23
forgot clearing vector and priorityQueue...easy logic...Ac in 2nd |
| Added by: | Paritosh Aggarwal |
| Date: | 2009-02-21 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE |
RSS