Photo by Benjamin Child on Unsplash

Meeting Room — Amazon Interview Problem

In this blog, we will go through a medium-tagged question. This question is frequently asked in interviews for Amazon & Facebook.

253. Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example:

Input: intervals = [[9,10],[4,9],[5,17]]
Output: 2

Approach:

We need to find how many concurrent meetings are happening. Once we have that info we can find the no of meeting rooms required. To find the concurrent meetings at any given time we need to know how many meetings’ start and end time covers that.

We can do a brute-force approach and go from min start time and go till maximum end time and check which time gives us maximum concurrent meeting.

To improve upon the brute force approach, what we can do is instead of doing it for all times, we only do it for the touchpoint timings namely, start and end. We know that overlap between meetings can only happen when another meeting starts and there is already a meeting started and has not ended yet. So if we encounter two consecutive start times that means we need two meeting rooms at that time. When we encounter an end time, it indicates we are done with a meeting and we don’t need that meeting room.

Code Implementation:

def minMeetingRooms(intervals):
    starts = sorted([interval[0] for interval in intervals])
    ends = sorted([interval[1] for interval in intervals])
    meet_count, cur_count = 0, 0
    s_ptr, e_ptr = 0, 0
    while s_ptr < len(intervals):
        if starts[s] < ends[e]:
            s_ptr += 1
            cur_count += 1
        else:
            e_ptr += 1
            cur_count -= 1
        meet_count = max(meet_count, cur_count)
    return meet_count

Time Complexity: O(NlogN) for sorting. While loop is a single pass of N.

Space Complexity: O(N) As we store the start and end time in array

Alternative Implementation:

We can keep track of the meeting end times. Whenever we see a meeting which has a start time smaller than the smallest meeting end time, we increase the count. Once we reach a start time which is greater than the end time of the meeting which is scheduled to end first, we remove that meeting’s end time as the meeting will be already ended by that time. We keep doing this till we reach the last meeting schedule. To keep track of meeting end times and remove the earliest one, we use heap data structure. As in min heap will always pop the smallest element, which here is the first meeting that ends.

from heapq import *
def minMeetingRooms( intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    res = 0
    for interval in intervals:
        if len(heap)==0 or heap[0]>interval[0]:
            res += 1
        else:
            heappop(heap)
        heappush(heap, interval[1])
    return res

Time Complexity: O(NlogN) for sorting. While loop is a single pass of N.

Space Complexity: O(N) As we store the start and end time in array

Happy Codding!!