Compute the Minimum Number of Meeting Rooms

Question

The question asks the candidate to determine the minimum number of meeting rooms required to accommodate all meetings given their start and end times.

Codemia · Accepted Answer

To solve the problem of computing the minimum number of meeting rooms required, we can utilize a greedy algorithm. The main idea is to sort the meetings based on their start times and then use a priority queue (min-heap) to track the end times of meetings currently in progress. This allows us to efficiently determine if a new meeting can use an existing room or if a new room is needed.

1. **Sort the meetings** by their start times.
2. Initialize a min-heap to keep track of end times of meetings.
3. Iterate through each meeting:
   - If the heap is not empty and the smallest end time is less than or equal to the start time of the current meeting, pop from the heap (meaning a room is freed).
   - Push the end time of the current meeting onto the heap.
4. The size of the heap at the end will give the minimum number of meeting rooms required.

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of meetings. The space complexity is O(n) for the heap, which may contain all meetings in the worst case.

```python
import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0

# Step 1: Sort the meetings in increasing order of their start times
    intervals.sort(key=lambda x: x[0])
    min_heap = []  # Initialize a heap

# Step 2: Add the first meeting's end time to the heap
    heapq.heappush(min_heap, intervals[0][1])

# Step 3: Iterate through the remaining meetings
    for i in range(1, len(intervals)):
        # If the room due to the earliest finished meeting is free, reuse it
        if min_heap[0] <= intervals[i][0]:
            heapq.heappop(min_heap)
        # Add the current meeting's end time to the heap
        heapq.heappush(min_heap, intervals[i][1])

# The size of the heap tells us the minimum rooms required
    return len(min_heap)
```
This code efficiently calculates the minimum number of meeting rooms required based on the provided meeting intervals.

Consider cases where:
- All meetings overlap completely, requiring as many rooms as there are meetings.
- Meetings that start and end at the same time, which should be handled properly by the algorithm. This solution accounts for such cases by managing the heap correctly.

Compute the Minimum Number of Meeting Rooms

Walmart Labs

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Walmart Labs Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string