Problem Statement
Given a list of intervals representing the start and end time of ’N’ meetings, find the minimum number of rooms required to hold all the meetings.
Example 1:
Meetings: [[1,4], [2,5], [7,9]]
Output: 2
Explanation: Since [1,4] and [2,5] overlap, we need two rooms to hold these two meetings. [7,9] can
occur in any of the two rooms later.
Example 2:
Meetings: [[1,4], [2,3], [3,6]]
Output:2
Explanation: Since [1,4] overlaps with the other two meetings [2,3] and [3,6], we need two rooms to
hold all the meetings.
Example 3:
Meetings: [[1,6], [2,3], [3,6]]
Output:2
Walkthrough
Our task here is basically to look for the maximum number of meetings that are currently running in parallel. If a meeting starts before previous meetings end, it means we need more meeting rooms to hold all the meeting.
Using a min heap to keep track of meeting rooms
We can use a min heap to keep track of the meeting rooms, where the meeting with the smallest end time should be at the top of the heap. Before we push a new meeting to the heap, we check whether there is any previous meeting that has ended. If there is any, we want to remove them from the heap as the room has been freed up.
Note: Remember to sort the meeting based on start time first for our algorithm to work properly.
