Minimum Meeting Rooms

You are given several test cases. In each test case, you are provided with N meetings represented by their start and end times. The objective is to determine the minimum number of conference rooms required so that all meetings can take place without overlapping.

The problem can be formally described as follows:

Given a list of meetings \(\{(s_1, e_1), (s_2, e_2), \dots, (s_N, e_N)\}\), find the smallest number \(k\) such that the meetings can be assigned to \(k\) rooms without any two overlapping in the same room. A meeting \((s_i, e_i)\) is said to overlap with another meeting \((s_j, e_j)\) if \(s_i < e_j\) and \(s_j < e_i\).

This problem is often solved using a greedy algorithm combined with a priority queue (or min-heap) to track the end times of the meetings.

inputFormat

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

• The first line contains an integer \(N\), the number of meetings.
• The next \(N\) lines each contain two integers representing the start and end times of a meeting.

It is guaranteed that the meeting times are given in integer format.

Example:

2
3
0 30
5 10
15 20
2
7 10
2 4

outputFormat

For each test case, output a single integer on a new line representing the minimum number of meeting rooms required.

Example Output:

2
1

## sample

2
3
0 30
5 10
15 20
2
7 10
2 4

2
1

</p>