Assign Meetings to the Minimum Number of Rooms

Question

The question asks the candidate to determine the minimum number of meeting rooms required to accommodate a set of meetings based on their start and end times.

Codemia · Accepted Answer

To solve the problem of assigning meetings to the minimum number of rooms, we can utilize a greedy algorithm combined with a min-heap. The idea is to sort the meetings by their start times and use a min-heap to keep track of the end times of the meetings currently in progress. This allows us to efficiently determine when a room becomes available.

1. **Sort the meetings** by their start time.
2. Initialize a min-heap to track the 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 current meeting's start time, pop the heap (indicating that a room has become available).
   - Push the current meeting's end time onto the heap.
4. The size of the heap at the end will represent the minimum number of rooms required.

The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of meetings. The space complexity is O(k), where k is the number of rooms needed, which is bounded by n in the worst case.

```python
import heapq

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

# Step 1: Sort the meetings by start time
    intervals.sort(key=lambda x: x[0])

# Step 2: Initialize a min-heap
    heap = []

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

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

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

Interviewers are looking for clarity in your thought process and how well you can adapt your solution to additional requirements. They want to see your problem-solving skills in action, particularly how you handle edge cases and optimize your solution for performance. Additionally, demonstrating a solid understanding of data structures and algorithmic principles is crucial.

Assign Meetings to the Minimum Number of Rooms

Uber

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

Uber 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