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

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

  • Space Complexity: O(N) For the two lists of start_time and end_time, it will take N spaces.

Written by

Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store