OLYMPUS DIGITAL CAMERA

Meeting Room Scheduling Problem

In our previous posts, we’ve covered topics like string, tree, linked list and so forth. In this week’s coding interview question, we’re going to discuss something different.

If you have taken many coding interviews, you will know that a lot of questions are quite close to real life projects and don’t have a focus on specific data structures. Some people find it hard at first glance. However, with some analysis, you’ll realize that there are no different from other questions.

In this post, we’ll mainly talk about interval problems and some common techniques you can use when getting stuck.

 

Question

Given a list of meeting times, checks if any of them overlaps. The follow-up question is to return the minimum number of rooms required to accommodate all the meetings.

Let’s start with an example. Suppose we use interval (start, end) to denote the start and end time of the meeting, we have the following meeting times: (1, 4), (5, 6), (8, 9), (2, 6).

In the above example, apparently we should return true for the first question since (1, 4) and (2, 6) have overlaps. For the follow-up question, we need at least 2 meeting rooms so that (1, 4), (5, 6) will be put in one room and (2, 6), (8, 9) will be in the other.

The meeting room scheduling problem was asked by Facebook very recently and there are quite a few similar problems.

 

Analysis

Again, if you haven’t seen this problem before, spend a couple of minutes to think about it.

Let’s start with the first question – check if there are overlaps. I used to interview people with a similar problem and I’ve seen that quite a few candidates tended to enumerate “all cases” with tons of if-else clause. In reality, you are never done because there are always some corner cases your algorithm won’t cover.

There are basically two suggestions here. First, it’s always recommended to start coding after you are confident enough about your solution. Many people like to write code while thinking, which won’t really work in an interview since you don’t have much time. If you think thoroughly about the enumeration approach, it shouldn’t be hard to know that it won’t work in certain cases.

Secondly, when you get stuck, a good approach is to manually try some examples and understand how it works. Let me explain this more. If you manually check if there’re overlaps in the above example, you’ll need to draw each interval in a 1-D space and check if any two intervals overlap. One lesson we learned from this example is that only two “nearby” intervals are able to overlap, which indicates that we may sort all of them and then only check nearby intervals.

 

Sort

In fact, sorting intervals by the start time is an extremely common approach in interval questions. After we sort all the intervals, we can just traverse and check if the next interval’s start point is larger than the current one’s end point.

There’s another way to do that. If you see the sorted intervals as an array of start and end points in order, you can keep a counter. Go over the points one by one in order. When you get a start point, increase the counter by one and decrease by one when it’s an end point. If there’s no overlap, the counter can never get above 1.

The time complexity of sorting is O(NlogN) and the checking overlap is O(N). So overall it’s O(NlogN).

 

Follow-up

How many meeting rooms do we need at least in order to accommodate all the meetings?

With all the analysis above, it shouldn’t be hard to solve the follow-up question. Think about this: if there’s a timestamp that has 3 intervals covered, we need at least 3 meeting rooms. Otherwise, at least two of those 3 meetings have conflict. With that in mind, we know that if we can find the timestamp with most intervals covered, then the number of covered intervals is the number of meeting rooms we need.

So how to calculate the maximum number of covered intervals? In fact, following the above counter analysis, the max value of the counter is the maximum number of covered intervals. This is because for a given timestamp if there are N unclosed start point in front it, this timestamp must be covered by N intervals.

Some people might find it hard to figure this out. And I’ll tell you that the solution doesn’t come from nowhere. If you try with several examples and draw them on a paper, you will realize how obvious it is.

 

Takeaways

The biggest thing in this post is to try with examples. Whenever you get stuck, you should consider trying few examples to understand how you can solve the problem as a human. In fact, you might be able to copy the same strategy in a program. Also, some examples can simplify the problem and make it easier to get the essence.

Another thing is that sorting and iterating over the sorted intervals are very common techniques in similar problems. For instance, another popular question is to merge a list of intervals that might have overlaps. After reading this post, you should be able to solve this question with no problem at all.

The post is written by Gainlo - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Share on Facebook5Tweet about this on TwitterShare on LinkedIn7Share on Reddit0

6 thoughts on “Meeting Room Scheduling Problem

  1. There’s an edge case where you have one time that extends at least to the end of the meeting times two elements in front of it.

    To avoid making the solution quadratic, I drew lines on a piece of paper to see the problem in front of me. That helped me realize that I can just maintain a reference to the meeting with the greatest end time so far, and check that against the start time.

  2. If you can have an extra array with one element for each hour, you need not sort the intervals. We can go through each interval and increase the reference count in the array. Once all the intervals are over, the maximum number of meeting room needed will be the maximum value in the array. And there is an overlap, if this maximum value is greater than one.

  3. It seems that only 2 rooms are needed to handle the case where timestamp covers 3 intervals. One room for (1, 4), (5, 6) and another for (2, 6)

    1. The counter approach mentioned above works well on it.
      s = [1, 2, 5, 8]
      e= [4, 6, 6, 9]
      If you pick the lower one amongst each of those start and end points until you fully iterate the arrays incrementing the counter when the lower point is a start point and decrementing it when the lower point is an endpoint, the maximum value of the counter reaches 2. This indicates the maximum number of intervals overlapping at any point of time is 2.

  4. Both of your approaches will not work if i and i+2 are overlapped .. for example, if the original intervals are (1, 4), (3, 6), (8, 9), (2, 6)
    then after sorting it’ll be (1, 4), (2, 6), (3, 6), (8, 9) .. so, here clearly we have 3 overlapping meetings your algorithms will record that 1 & 2 are overlapped, and 2 & 3 are overlapped, but won’t detect 1&3.
    I agree with Ravi who used an array representing the hours ..etc

Leave a Reply

Your email address will not be published. Required fields are marked *