Meeting Room Scheduling Problem

Meeting Room Scheduling Problem In our previous posts, weve covered topics like string, tree, linked list and so forth. In this weeks coding interview question, were 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 dont have a focus on specific data structures. Some people find it hard at first glance. However, with some analysis, youll realize that there are no different from other questions. In this post, well 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. Lets 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 havent seen this problem before, spend a couple of minutes to think about it. Lets start with the first question check if there are overlaps. I used to interview people with a similar problem and Ive 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 wont cover. There are basically two suggestions here. First, its always recommended to start coding after you are confident enough about your solution. Many people like to write code while thinking, which wont really work in an interview since you dont have much time. If you think thoroughly about the enumeration approach, it shouldnt be hard to know that it wont 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 therere overlaps in the above example, youll 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 intervals start point is larger than the current ones end point. Theres 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 its an end point. If theres 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 its 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 shouldnt be hard to solve the follow-up question. Think about this: if theres 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 Ill tell you that the solution doesnt 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.