# Ace the Coding Interview — LeetCode 253

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.

# Problem Analysis

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.

# Algorithm

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

# BigO Analysis

- Time Complexity:
`O(NlogN)`

For N meetings, the sorting of`start_time`

and`end_time`

will take NlogN. And the loop over the`start_time`

will take N. So total time is NlogN. - Space Complexity:
`O(N)`

For the two lists of`start_time`

and`end_time`

, it will take N spaces.