Meeting Rooms Problem (How To Solve Minimum & Max)

Meeting Rooms Problems & Solutions

What are Meeting Rooms Problems?

Meeting rooms problems typically ask you to design an algorithm to determine whether a given set of meeting room requests can be scheduled without any conflicts. You might be asked how many rooms would be required to conduct a certain number of meetings (a minimum meeting rooms problem) or you might be asked how many meetings could be conducted in a given number of rooms (a maximum meeting rooms problem). These are familiar problems in the real world, and can be approached using simple data structures such as lists, or advanced ones like priority queues.

An Example of a Meeting Rooms Problem

Given a list of meetings, represented as tuples with a start and an end time, determine the minimum number of rooms required to schedule all the meetings.

Input: meetings = [[5, 10], [2, 3]]
Output: 1

Input: meetings = [[1, 3], [5, 7], [4, 6], [7, 9], [9, 10]]
Output: 2

Constraints

How to Solve the Meeting Rooms Problem

This problem is phrased like a real-world problem because it really is one! Unlike many interview questions where a large part of the task is to make concrete what is presented as a highly ambiguous question, this problem offers us a tangible scenario from the outset.

Let's use this to our advantage and consider how we would approach this problem without a computer. Remember to focus on exactly what the problem is asking for: we want to find the minimum number of rooms required to book all the meetings. If no meetings overlap, we would only need one room, since once a meeting is over that room is freed up. But if more than one meeting is occurring at a given time, then we would need additional rooms. We can think of rooms as some generic, quantifiable resource, and the meetings as tasks or events that consume a resource and release it once complete.

Scheduling tasks is often solved with the help of a calendar, or some other visual aid, so let's follow this line of thinking. One useful way to visualize events is using a timeline!

Consider this example:

Plaintext

meetings = [[7, 9], [1, 3], [5, 7], [4, 6], [9, 10]]

Above this timeline we stack all the meetings from our input - suddenly it becomes clear how many rooms we would need over the course of the day, since we can see the overlaps. At no point do we have more than two overlapping meetings - so we'll need a minimum of two rooms!

Approach 1: Two Lists

One way to implement this algorithm is to use two sorted lists that track the meeting start and end times respectively, iterating over each list with a unique pointer starting at the beginning of each list.

When we iterate over "startTimes" with the pointer i, we are considering each meeting in the order in which it begins, simulating the timeline from our strategy above. So, with i starting at the first index, we know that a meeting has begun and a room is needed. Pointer j on the "endTimes" list will always indicate the next meeting that is ending, and therefore the next time that a room is made available.

Meeting Rooms Python, JavaScript and Java Solutions - Two Lists

Python

class Solution:
    def minMeetingRooms(self, meetings: List[List[int]]) -> int:
        if not meetings: return 0

start_times = []
        end_times = []

for [start, end] in meetings:
            start_times.append(start)
            end_times.append(end)

start_times.sort()
        end_times.sort()

j = 0
        num_rooms = 0

for i in range(len(start_times)):
            if start_times[i] < end_times[j]:
                num_rooms += 1
            else:
                j += 1

return num_rooms

Time/Space Complexity

Approach 2: Priority Queue

Although the true benefit of a priority queue is the ability to sort a partial dataset, it is still a highly convenient data structure when dealing with sorted data.

As a reminder, a priority queue is essentially a data structure that performs a re-sort whenever its contents change. This can be especially useful when we have a dynamic data set, and when we need to know what the smallest or largest element is in constant time.

Meeting Rooms Python, JavaScript and Java Solutions - Priority Queue

Python

class Solution:
    def minMeetingRooms(self, meetings: List[List[int]]) -> int:
        if not meetings: return 0

meetings.sort(key = lambda x: x[0])

rooms = []
        heapq.heappush(rooms, meetings[0][1])

for [start, end] in meetings[1:]:
            if rooms[0] <= start:
                heapq.heappop(rooms)

heapq.heappush(rooms, end)

return len(rooms)

Time/Space Complexity

Practice the Meeting Rooms Problem With Our AI Interviewer

Start AI Interview

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies.