Feature #1: Find Meeting Rooms
We'll cover the following...
Description
To develop this project’s first feature, we are given a set of meeting times. Our job is to implement a solution that can identify the number of meeting rooms needed to schedule the required meetings. Each meeting time will contain a start_time
and an end_time
that are both positive integers.
Our list of meetings times looks like the following: [[2, 8], [3, 4], [3, 9], [5, 11], [8, 20], [11, 15]]
. If we schedule each meeting in a separate room, that would require six rooms. However, we want to use the minimum number of rooms possible. In the example, we can see that the first three meetings, [2, 8]
, [3, 4]
, and [3, 9]
, are overlapping. Therefore, each of them will require a separate meeting room.
Take a look at the illustration below to see how we can schedule all the meetings in just three rooms:
Solution
We can use a heap or priority queue to keep the meeting timings, where the key would be the end_time
of each meeting. This way, we can check if any room is free or not by simply checking the heap’s topmost element. The room at the top of the heap would get free the earliest out of all the other rooms currently occupied.
If the room we obtain from the top of the heap isn’t free ...
Create a free account to view this lesson.
By signing up, you agree to Educative's Terms of Service and Privacy Policy