MEDIUM

DATA STRUCTURES AND ALGORITHMS

HEAPSMAPS

Written By

Tom Wagner

Kenny Polyak

Introduction Meeting Rooms

The Meeting Rooms problem requires designing an algorithm to determine whether a given set of meeting room requests can be scheduled without any conflicts. This is a familiar problem in the real world, and can be approached using simple data structures such as lists, or advanced ones like priority queues.

Problem Meeting Rooms

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,000`

`0 <= start <= 10,000`

`0 <= end <= 10,000`

Solution Meeting Rooms

Watch Someone Solve Meeting Rooms

Google InterviewJavaScript Interview

Advance this person to the next round?

Technical Skills:

2/4

Problem Solving Ability:

1/4

Communication Ability:

2/4

Show Transcript

Watch more mock interviews

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.

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.

```
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_rooms
```

```
1class 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_rooms
```

- Time complexity:
`O(n*log(n))`

- Space complexity:
`O(n)`

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.

```
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 complexity:
`O(n*log(n))`

- Space complexity:
`O(n)`

MEDIUM

Data Structures and Algorithms

Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

HEAPSTREES

Watch 1 interview

MEDIUM

Data Structures and Algorithms

Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

ARRAYSSORTINGHASH MAPSSEARCH

Watch 1 interview

EASY

Data Structures and Algorithms

Reverse Linked List

Given the head of a linked list, reverse the list and return the new head.

LINKED LISTS

Watch 2 interviews

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.

Ready to practice with a mock interview?

Book mock interviews with engineers from Google, Facebook, Amazon, or other top companies. Get detailed feedback on exactly what you need to work on. Everything is fully anonymous.