Compute the Minimum Number of Meeting Rooms

Question

The candidate is asked 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 determining the minimum number of meeting rooms required, we need to consider the start and end times of each meeting. The goal is to find the maximum number of meetings that overlap at any given time, as this will dictate the number of rooms needed.

We can use a greedy algorithm combined with a min-heap (or priority queue) to efficiently track the end times of meetings. The basic idea is to sort the meetings by their start times and then iterate through them, using the heap to manage the end times of meetings currently in progress.

1. Sort the meetings by their start times.
2. Initialize a min-heap to keep track of end times.
3. For each meeting, check if the room with the earliest end time is free (i.e., its end time is less than or equal to the current meeting's start time).
4. If it is free, remove it from the heap; if not, add a new room (i.e., push the current meeting's end time onto the heap).
5. The size of the heap at the end will be the minimum number of meeting rooms required.

```python
import heapq

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

# Create a list of start and end times
    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])

room_count = 0
    end_index = 0

for start in starts:
        # If the meeting starts after the earliest meeting ends, free up a room
        if start >= ends[end_index]:
            end_index += 1
        else:
            room_count += 1

return room_count
```
This code sorts the start and end times and uses a two-pointer technique to determine the number of rooms needed.

The time complexity of this solution is O(N log N) due to the sorting of the meetings, where N is the number of meetings. The space complexity is O(N) for storing the start and end times. This approach efficiently handles the scheduling problem while ensuring that we minimize the number of meeting rooms used.

Compute the Minimum Number of Meeting Rooms

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Amazon 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