TWOPROF - Two Professors
There are two professors at the great Academy of X that really do not get along with each other. In order not to reveal their names, we will call them 1 and 2. The Academy employs exactly n professors, each of them has to give exactly one lecture. As their schedules are rather tight (they are professors, remember?), the starting and the ending time of each lecture is already fixed. However, it is not yet fixed where each lecture will take place. Obviously, it is impossible to schedule two lectures in the same room if their durations overlap; on the other hand, it is possible if one of them starts exactly at the same time that the other one ends. Your tasks is to find the minimal number of rooms allowing to arrange all the lectures. But know that professors 1 and 2 hate each other so much that they will never give their lectures in the same room.
The input contains several test cases. The first line contains the number of test cases t (t <= 250). Each test begins with a line containing the number of professors n (2 <= n <= 100000). Next n lines follow, i-th of which contains two integers starti and endi (0 <= starti < endi <= 1000000000), the starting and the ending time of the lecture that the i-th professor gives, respectively.
For each test case output the minimal number of rooms necessary to schedule all the lectures.
Input: 4 2 0 10 10 20 3 0 10 10 20 10 20 5 4 14 3 13 2 12 1 11 0 10 4 0 10 10 20 20 30 30 40 Output: 2 2 5 2
Warning: enormous input/output data, be careful with certain languages
Why i'm getting WA at test case 3 ?
here given that 1st and 2nd professors hate each other and dont want to teach in the same room
how is the output for 1st case is 2 ?