Recent interview question asked by Google and Amazon.
In this post, we are going to discuss the leetcode problem no. 253 — Meeting Rooms II. This problem is recently asked in Google and Amazon interviews.
The input of the problem is a list of meeting schedules. Each meeting schedule is represented by a list of two items, with the first item as the starting time of a meeting, and the second item as the ending time of the meeting.
The expected output of the problem is an integer, which is the minimum number of meeting rooms required to fulfill the meeting schedules.
For example, we can have an input as
[[0, 30],[5, 10],[15, 20]], which means there are 3 meetings: the first meeting starts at time 0 and ends at time 30; the second meeting starts at time 5 and ends at time 10; and the third meeting starts at time 15 and ends at time 20.
The output for the above input will be
2. Because from time 0 to 5, we only need 1 room for the first meeting; from time 5 to 10, we need 2 rooms for both the first and second meeting; from time 10 to 15, we again only need 1 room for the first meeting; from time 15 to 20, we need 2 rooms for the first and third meeting; and from time 20 to 30, we need 1 room for the first meeting. So the minimum number of rooms needed to fulfill all the meetings is 2.
For this problem, we need to find the maximum number of overlaps for all the meetings. This is also equivalent to find the number of meetings that have not finished, when a new meeting starts.
In order to get that, we need the following variables:
- start_times: sorted list (ascending) which stores the starting times of the meetings
- end_times: sorted list (ascending) which stores the ending times of the meetings
- rooms: current number of rooms needed to fulfill the meetings up to now
- max_rooms: maximum number of rooms needed to fulfill all the meetings
Then starting from the first start_time and first end_time:
- If the start_time is smaller than the end_time, it means all the previous meeting are still on going when the next one starts. So the current number of rooms needs to increase by 1 to fulfill the new meeting. And Then we need to check the next start_time with the current end_time.
- If the start_time is larger than or equal to the end_time, it means one of the previous meetings has ended when the next one starts. So the current number of rooms needs will be decreased by 1. And Then we need to check the next end_time with the current start_time.
Implementation in Python
- Time Complexity:
O(NlogN)For N meetings, the sorting of
end_timewill take NlogN. And the loop over the
start_timewill take N. So total time is NlogN.
- Space Complexity:
O(N)For the two lists of
end_time, it will take N spaces.