Maximum Non-Overlapping Intervals

Maximum Non-Overlapping Intervals

You are given T test cases. In each test case, you will be provided with a set of intervals defined by their start and end times. Your task is to compute the maximum number of non-overlapping intervals that can be selected from each test case.

Two intervals \( (s_1, e_1) \) and \( (s_2, e_2) \) are considered non-overlapping if \( s_2 \ge e_1 \) when the intervals are sorted by their end times. A common greedy strategy is to sort the intervals by their end times and then select the next interval whose start time is greater than or equal to the end time of the last chosen interval.

For instance, consider the condition for selecting an interval \( (s, e) \) after the previously selected interval ends at \( E \):

\( s \ge E \)

This problem challenges your ability to implement a greedy algorithm to efficiently determine the optimal solution.

inputFormat

The first line contains an integer T, representing the number of test cases.

For each test case:

• The first line contains an integer N, the number of intervals.
• Each of the next N lines contains two space-separated integers representing the start and end time of an interval.

Input is provided via standard input (stdin).

outputFormat

For each test case, print a single line containing the maximum number of non-overlapping intervals that can be selected.

Output should be written to standard output (stdout).

2
3
1 4
2 5
5 8
4
1 3
2 4
3 5
5 7

2
3