Maximum Non-Overlapping Consultation Intervals

You are given multiple test cases, each containing a list of consultation intervals defined by their start and end times. Your task is to determine the maximum number of non-overlapping intervals that can be attended in each test case.

The problem is analogous to the interval scheduling maximization problem. Mathematically, given a set of intervals \(\{(S_i, E_i)\}_{i=1}^N\), the goal is to select a subset \(I\) such that no two intervals in \(I\) overlap and \(|I|\) is maximized. The well-known greedy approach involves sorting the intervals by their end times \(E_i\) and iteratively picking intervals that start after or at the end of the last selected interval.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer \(T\) denoting the number of test cases.
• For each test case, the first line contains an integer \(N\), the number of intervals.
• This is followed by \(N\) lines, each containing two space-separated integers \(S_i\) and \(E_i\) representing the start and end times of an interval.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of non-overlapping intervals that can be attended.

1
4
1 4
2 3
3 5
7 8

3