LC: Meeting Rooms II - spiralgo/algorithms GitHub Wiki

Meeting Rooms II

The Essence: I think the simplest intuition to solve this question might be like that:

• If there is just 1 meeting, we would need just 1 room.
• Even if there is more than 1 meeting; if the next meetings start after the end of the previous ones, then again we would need just 1 room. (i.e. in the case without any overlapping)
• If some meeting ends after some meeting with a larger start time has started, that indicates overlapping.
• It can then be inferred that for each interval, if the current earliest interval ending is larger than the starting time, then more rooms are needed.

Details:

Since the given intervals are not sorted, the utilization of this procedure requires either sorting or priority queues, where end times and start times need to be separated. For the array sorting case, a two pointer approach for the two arrays is also useful.

Further explanation and code can be found here: https://github.com/spiralgo/algorithms/pull/288