Minimum Meeting Rooms

You are given a list of meeting time intervals, each interval represented as a pair of integers start and end. Your task is to determine the minimum number of conference rooms required so that all meetings can take place without any conflict.

For each meeting interval \( (s_i, e_i) \), a conference room can only be used by one meeting at a time. Two meetings can share the same room if one ends exactly when the other begins. The goal is to find the maximum number of overlapping meetings at any time, which is equivalent to the minimum number of rooms required.

The key idea is to sort the start times and end times separately and then simulate the arrival of meetings. The formula to update the rooms is essentially:

[ used_rooms = used_rooms + 1 \quad \text{if } start_time < end_time, \quad \text{otherwise } used_rooms = used_rooms - 1 ]

Finally, the answer is the maximum value of used_rooms encountered during this process.

inputFormat

The first line contains an integer \( n \) representing the number of meetings. Each of the next \( n \) lines contains two space-separated integers \( s \) and \( e \) denoting the start and end times of a meeting.

outputFormat

Output a single integer that represents the minimum number of conference rooms required to accommodate all the meetings.

## sample

3
1 4
2 5
7 9

2

</p>