Solution: Problem Challenge 1: Minimum Meeting Rooms

Blind 75

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: [[6,7], [2,4], [8,12]]
Output: 1
Explanation: None of the meetings overlap, therefore we only need one room to hold all meetings.

Example 3:

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 4:

Meetings: [[4,5], [2,3], [2,4], [3,5]]
Output: 2
Explanation: We will need one room for [2,3] and [3,5], and another room for [2,4] and [4,5].

Here is a visual representation of Example 4:

Constraints:

1 <= meetings.length <= 104
0 <= starti < endi <= 106

Solution

Let’s take the above-mentioned example (4) and try to follow our Merge Intervals approach:

Meetings: [[4,5], [2,3], [2,4], [3,5]]

Step 1: Sorting these meetings on their start time will give us: [[2,3], [2,4], [3,5], [4,5]]

Step 2: Merging overlapping meetings:

[2,3] overlaps with [2,4], so after merging we’ll have => [[2,4], [3,5], [4,5]]
[2,4] overlaps with [3,5], so after merging we’ll have => [[2,5], [4,5]]
[2,5] overlaps [4,5], so after merging we’ll have => [2,5]

Since all the given meetings have merged into one big meeting ([2,5]), does this mean that they all are overlapping and we need a minimum of four rooms to hold these meetings? You might have already guessed that the answer is NO! As we can clearly see, some meetings are mutually exclusive. For example, [2,3] and [3,5] do not overlap and can happen in one room. So, to correctly solve our problem, we need to keep track of the mutual exclusiveness of the overlapping meetings.

We can conclude that we need to keep track of the ending time of all the meetings currently happening so that when we try to schedule a new meeting, we can see what meetings have already ended. We need to put this information in a data structure that can easily give us the smallest ending time. A Min Heap would fit our requirements best.

Step-by-step Algorithm

Check for Empty Input:
- If the list of meetings is empty or null, return 0, as no rooms are needed.
Sort Meetings by Start Time:
- Sort the list of meetings based on their start times. This helps in processing meetings in the order they begin.
Initialize Min-Heap:
- Create a priority queue (minHeap) to store the meeting intervals and sort them by end times of the meetings. This helps in efficiently finding the earliest ending meeting that can be replaced with a new meeting.
Process Each Meeting:
- Iterate through the sorted list of meetings.
  - For each meeting, check if the start time of the current meeting is greater than or equal to the earliest ending meeting in the minHeap.
  - If yes, remove the earliest ending meeting from the minHeap, as the room can be reused.
  - Add the current meeting's end time to the minHeap.
Track Maximum Rooms Needed:
- Keep track of the maximum size of the heap during the iteration. This size represents the minimum number of rooms required, as it shows the maximum number of concurrent meetings.
Return the Result:
- Return the maximum size of the heap as the result, representing the minimum number of meeting rooms needed.

Algorithm Walkthrough

Given input: [[4, 5], [2, 3], [2, 4], [3, 5]]

Check for Empty Input:
- The list is not empty, so we proceed.
Sort Meetings by Start Time:
- Sorted meetings: [[2, 3], [2, 4], [3, 5], [4, 5]]
Initialize Min-Heap:
- Initialize an empty priority queue (minHeap).
Process Each Meeting:
- Meeting [2, 3]:
  - minHeap is empty, so add the meeting [2, 3] to the heap.
  - minHeap: [[2, 3]]
  - Max rooms needed so far: 1
- Meeting [2, 4]:
  - Start time 2 is less than the earliest end time 3, so add the [2, 4] to the minHeap.
  - minHeap: [[2, 3], [2, 4]]
  - Max rooms needed so far: 2
- Meeting [3, 5]:
  - Start time 3 is equal to the earliest end time of the meeting [2, 3], so remove [2, 3] from the heap and add the meeting [3, 5].
  - minHeap: [[3, 5], [2, 4]]
  - Max rooms needed so far: 2
- Meeting [4, 5]:
  - Start time 4 is equal to the earliest end time 4, so remove [2, 4] from the heap and add the end time [4, 5].
  - minHeap: [[3, 5], [4, 5]
  - Max rooms needed so far: 2
Return the Result:
- Minimum meeting rooms required: 2

Code

Here is what our algorithm will look like:

Python3

Time Complexity

The time complexity of the above algorithm is $O(N*logN)$ ), where ‘N’ is the total number of meetings. This is due to the sorting that we did in the beginning. Also, while iterating the meetings we might need to poll/offer meeting to the priority queue. Each of these operations can take $O(logN)$ . Overall our algorithm will take $O(NlogN)$ .

Space Complexity

The space complexity of the above algorithm will be O(N) which is required for sorting. Also, in the worst case scenario, we’ll have to insert all the meetings into the Min Heap (when all meetings overlap) which will also take O(N) space. The overall space complexity of our algorithm is O(N).