Meeting Rooms Allocation

You are given a list of meetings, where each meeting is represented by its start time and end time. The task is to determine the minimum number of conference rooms required to schedule all the meetings such that no two meetings in the same room overlap.

Explanation: Each meeting is defined by a time interval \( [s, e] \). Two meetings can be scheduled in the same room if and only if the start time of one meeting is not less than the end time of the other meeting. One efficient approach to solve this problem is to sort the meetings by their start times and then use a min heap to keep track of the end times of meetings currently taking place. The size of the heap will indicate the number of rooms required.

Algorithm Outline:

• Sort all meetings based on their starting times.
• Use a min heap (priority queue) to track the end times of meetings currently scheduled in rooms.
• For each meeting, if the meeting's start time is at least the minimum end time in the heap, pop from the heap (freeing up a room) and add the current meeting's end time. Otherwise, add the current meeting's end time to the heap.
• The number of rooms required is equal to the size of the heap after processing all meetings.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains a single integer \(N\) representing the number of meetings. The next \(N\) lines each contain two space-separated integers \(s\) and \(e\), where \(s\) is the start time and \(e\) is the end time of a meeting.

Note: \(N\) can be zero, meaning there are no meetings.

outputFormat

Output a single integer to standard output (stdout), which is the minimum number of conference rooms required to schedule all the meetings without any conflicts.

3
1 4
2 5
6 8

2