Maximum Non-Overlapping Events

You are given a list of events, each with a start time and an end time. Your task is to determine the maximum number of events that can be scheduled without overlapping. Two events are considered non-overlapping if the start time of one event is greater than or equal to the finish time of the previously selected event.

In mathematical notation, given events with intervals \( [s_i, e_i] \), you need to select a subset \( S \) of events such that for any two events \( a \) and \( b \) in \( S \) (with \( a \neq b \)), either \( s_a \geq e_b \) or \( s_b \geq e_a \) holds. The goal is to maximize the size of \( S \). The optimal approach involves sorting the events by their ending times and then greedily selecting events.

inputFormat

The input begins with an integer ( T ) representing the number of test cases. Each test case starts with an integer ( N ), the number of events. This is followed by ( N ) lines, each containing two integers representing the start time and end time of an event respectively.

outputFormat

For each test case, output a single integer on a new line indicating the maximum number of non-overlapping events that can be scheduled.## sample

1
3
1 3
2 5
4 6

2