Feature #1: Find Meeting Rooms
Implementing the "Find Meeting Rooms" feature for our "Google Calendar" project.
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 startTime and an endTime that are both positive integers.
Our array 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 endTime 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 yet, then this means no other room is free either. So, we can allocate a new room in this condition.
Here is how the implementation will take place: ...