My Calendar III

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.) You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarEvents class:

MyCalendarEvents() Initializes the object.

int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Note:

Here the start of the event is included while the end is not as part of the slot i.e. the slot end right before the end.

For Example

Input:
["MyCalendarEvents", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]  
Output:
[null, 1, 1, 2, 3, 3, 3]

Explanation:
MyCalendarEvents myCalendarEvent = new MyCalendarEvents();
myCalendarEvent.book(10, 20); // return 1, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarEvent.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarEvent.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarEvent.book(5, 10); // return 3
myCalendarEvent.book(25, 55); // return 3

Input Format:

The first line determines the number of test cases that would be given in the problem.
The first line of each test case contains the integer ‘N’ which denotes the number of events that are going to be there.
Each ‘N’ line of input contains two space-separated integers where the first value is the start of the slot of the events ‘start’ while the second integer is the end of the slot of the events ‘end’.

Output Format:

For every test case, return an integer k representing the maximum k-booking between all the previous events.

Print the output of each test case in a separate line.

Constraint :

1 <= T <= 5
1 <= N <= 1000
0 <= start < end <= 10^9

Where ‘start’ is the start of the slot of the events ‘columns’ is the number of columns.

Time Limit: 1 sec