BYTESE2 - The Great Ball
The Great Ball (5 points) 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 No||Enters at||Leaves at|
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.
A total of T lines each of them containing a single integer, denoting the maximum number of dancers during the ball.
Input: 1 5 1 7 2 4 6 9 3 8 5 10 Output: 4
Hint -> Sorting + Min-Priority Queue
Coordinate compression + Prefixsum!!
got an AC!! after two wrong ans using two pointers technique btw nice question :)
Testcases really are weak
Coordinate compression + Prefixsum!! AC 0.00s
got AC using a simple array...
Can't get it.. why two same code gives different verdict, one gives TLE. After a moment when I resubmit it... it shows AC.
maps got ac in 0.00 sec!
Store each entrance and exit as an event (a change in number of people which is +1 or -1, and a time the event occurs). Then process the events in order of time and keep track of the number of people after each event.
|Added by:||Paritosh Aggarwal|
|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 qobi SCM guile ST WHITESPACE|