Maximum Non-overlapping Events Scheduling

You are given a sequence of test cases, where each test case consists of a set of events. Each event is represented by its start time and end time. Your task is to determine the maximum number of non-overlapping events that can be attended. Two events are non-overlapping if the start time of an event is greater than or equal to the finish time of the previously attended event, i.e., if an event starts at time \(s\) and the previous event finished at \(f\), then the event can be attended if \(s \ge f\).

Note: The optimal solution can be achieved by sorting the events based on their finish times and then using a greedy algorithm to select the maximum number of events.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n
start1 end1
start2 end2
... (n lines)
... (repeat the above for T test cases)

Where:

• \(T\) is the number of test cases.
• For each test case, \(n\) is the number of events.
• Each event is described by two integers: the start and end times.

outputFormat

For each test case, output a single line to standard output (stdout) containing one integer: the maximum number of non-overlapping events that can be attended.

## sample

2
3
10 20
15 25
20 30
3
2 3
3 4
1 2

2
3

</p>