What are Meeting Rooms Problems?
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
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
1 <= meetings.length <= 10,0000 <= start <= 10,0000 <= end <= 10,000
How to Solve the Meeting Rooms Problem
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:
meetings = [[7, 9], [1, 3], [5, 7], [4, 6], [9, 10]] 1meetings = [[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!
How can we translate this visual process into an algorithm? Well, to mimic a timeline, we would need to process the meetings in the order in which they occur, so our input will need to be sorted. Considering that we need to know what the first meeting is, it will be helpful to sort the meetings by start time. Then, as we iterate through each meeting, the task becomes to determine the maximum number of overlaps over the course of the day.
Let's look at two approaches to implement the above strategy. Since both involve sorting the input list and using an additional data structure to store meeting times, we can't beat O(n log n) time complexity and O(n) space complexity.
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.
When i moves forward, we know that another meeting is beginning - but how can we know if we need an additional room? Well, if a currently running meeting ends before this meeting begins, then we can use the same room for both meetings; otherwise, we'll need to get another room.
Using this logic, we can compare the value of i - the start of the current meeting - with the value of j - the next ending meeting and thus the next time a room is available - to determine the number of overlapping meetings. If the current start time is smaller than the next upcoming end time, then we know we will need an additional room, so we increment our rooms count. If not, we move the end times pointer forward, indicating that a meeting has ended and room has been freed, and we don't increment the rooms count.
We increment roomsCount if the value at i is smaller than the value at j, since the next ending room is not yet free. In other words, there's an overlap, so we definitely need another room.
When the value at i is greater than or equal to the value at j, we increment j, then continue iterating on i. Once the iteration is complete, return the count of rooms.
Meeting Rooms Python, JavaScript and Java Solutions - Two Lists
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:
end_index += 1
return num_rooms1class Solution:
2 def minMeetingRooms(self, meetings: List[List[int]]) -> int:
3 if not meetings: return 0
4
5 start_times = []
6 end_times = []
7
8 for [start, end] in meetings:
9 start_times.append(start)
10 end_times.append(end)
11
12 start_times.sort()
13 end_times.sort()
14
15 j = 0
16 num_rooms = 0
17
18 for i in range(len(start_times)):
19 if start_times[i] < end_times[j]:
20 num_rooms += 1
21 else:
22 end_index += 1
23
24 return num_roomsTime/Space Complexity
- Time complexity:
O(n*log(n)) - Space complexity:
O(n)
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.
How does this help our meeting rooms problem? Remember that a room is released once a meeting is complete - so we can use a priority queue to track the currently used rooms, and quickly determine if an upcoming meeting will overlap with any of the currently running meetings.
Meeting Rooms Python, JavaScript and Java Solutions - Priority Queue
class Solution:
def minMeetingRooms(self, meetings: List[List[int]]) -> int:
if not meetings: return 0
# sort meetings in ascending order by start time
meetings.sort(key = lambda x: x[0])
# initialize heap and add the first meeting's end
rooms = []
heapq.heappush(rooms, meetings[0][1])
for [start, end] in meetings[1:]:
# top of the heap is the meeting that will end soonest
# we can remove it if it ends before the next meeting starts
if rooms[0] <= start:
heapq.heappop(rooms)
heapq.heappush(rooms, end)
# the size of the heap at the end is the minimum rooms required
return len(rooms)1class Solution:
2 def minMeetingRooms(self, meetings: List[List[int]]) -> int:
3 if not meetings: return 0
4
5 # sort meetings in ascending order by start time
6 meetings.sort(key = lambda x: x[0])
7
8 # initialize heap and add the first meeting's end
9 rooms = []
10 heapq.heappush(rooms, meetings[0][1])
11
12 for [start, end] in meetings[1:]:
13 # top of the heap is the meeting that will end soonest
14 # we can remove it if it ends before the next meeting starts
15 if rooms[0] <= start:
16 heapq.heappop(rooms)
17
18 heapq.heappush(rooms, end)
19
20 # the size of the heap at the end is the minimum rooms required
21 return len(rooms)Time/Space Complexity
- Time complexity:
O(n*log(n)) - Space complexity:
O(n)
Practice the Meeting Rooms Problem With Our AI Interviewer
Practice the Meeting Rooms Problem With Our AI Interviewer
Watch These Related Mock Interviews
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. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
