253. Meeting Rooms II

How to solve Meeting Rooms II (LeetCode 253): the approach in brief

The problem

You are given an array of meeting time intervals intervals where intervals[i] = [starti, endi] represents the start and end times of the ith meeting. All meetings are scheduled in the same building, and a meeting can use any available conference room.

Pattern

Meeting Rooms II is a Heap (Priority Queue) Patterns problem, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern. The pattern covers top K elements, K-way merge, two heaps for median, and scheduling

Solve scheduling and optimization problems using priority queue with greedy approach.

Approach outline

1. Think about how we would approach this problem in a very simplistic way. We will allocate rooms to meetings that occur earlier in the day v/s the ones that occur later on, right?
2. If you've figured out that we have to <b>sort</b> the meetings by their start time, the next thing to think about is how do we do the allocation? <br>There are two scenarios possible here for any meeting. Either there is no meeting room available and a new one has to be allocated, or a meeting room has freed up and this meeting can take place there.
3. An important thing to note is that we don't really care <b>which</b> room gets freed up while allocating a room for the current meeting. As long as a room is free, our job is done. <br><br>We already know the rooms we have allocated till now and we also know when are they due to get free because of the end times of the meetings going on in those rooms. We can simply check the room which is due to get vacated the earliest amongst all the allocated rooms.

Complexity

The reference solution runs in O(n log n) time and O(1) space.

Asked at

Meeting Rooms II has been reported in interviews at Amazon, Bloomberg, Facebook, Google, Microsoft, Oracle, Uber, Yandex.