Minimum Number of Rooms for Workshops

You are given several test cases. In each test case, there are a certain number of workshops, and each workshop is represented by its start and end times. Your task is to determine the minimum number of rooms required so that all the workshops can be scheduled without any overlapping.

Formally, for each test case you are given an integer \( n \) and \( n \) pairs of integers \( (s_i,e_i) \) representing the start and end time of the workshops. You need to compute the minimum number of rooms required such that no two workshops that share a room overlap in time.

The problem can be formulated as follows:

\[ \text{min_rooms} = \min\{ k : \text{all workshops can be assigned to one of } k \text{ rooms with no overlaps} \} \]

Hint: Use a greedy strategy with a min-heap (priority queue) to track the earliest ending workshop in each room.

inputFormat

The first line of input contains an integer \( T \) denoting the number of test cases. For each test case:

• The first line contains an integer \( n \), the number of workshops.
• The next \( n \) lines each contain two integers \( s \) and \( e \) representing the start and end times of a workshop.

Input is provided via standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the minimum number of rooms required to schedule all the workshops. The output should be printed via standard output (stdout).

## sample

2
3
1 4
2 5
6 8
4
1 3
2 4
3 5
4 6

2
2

</p>