Non-overlapping Workshops

Given a set of workshops, each with a starting time and an ending time, determine the maximum number of workshops an employee can attend without any overlap. A workshop is considered non-overlapping if its start time is not earlier than the end time of the previously attended workshop.

Formally, given a set of workshops \(\{(s_i, e_i)\}_{i=1}^{n}\) where \(s_i\) and \(e_i\) denote the start and end times of the \(i\)-th workshop, find the maximum \(k\) such that there exists a sequence of workshops \(\{w_{i_1}, w_{i_2}, \dots, w_{i_k}\}\) satisfying \(e_{i_j} \leq s_{i_{j+1}}\) for all \(1 \leq j

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(N\) representing the number of workshops. Each of the following \(N\) lines contains two space-separated integers \(s\) and \(e\) representing the start time and end time of a workshop.

outputFormat

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

1
0

0