The question
Given a list of meetings as intervals, how many rooms do you need so no two meetings share a room at the same time? The answer is the maximum number of meetings active at once, also called the maximum overlap.
Two timelines
A clean solution separates the timeline of starts from the timeline of ends.
- Sort all start times and all end times independently.
- Walk both lists with two pointers.
- When the next start is before the next end, a meeting begins, so increase the room count and advance the start pointer.
- Otherwise a meeting has ended, so advance the end pointer and free a room.
Track the largest room count you ever reach. That peak is the answer.
Why peak overlap equals rooms
Every meeting active at the busiest instant needs its own room, so you cannot do with fewer. And you never need more, because at any other instant the demand is lower. The peak of the active counter is exactly the requirement.
A heap variant
You can also sort meetings by start and keep a min heap of end times. The heap size at its largest is the room count, since popping ends that are already over reuses rooms.
Key idea
The minimum room count equals the peak number of meetings overlapping at any instant, found by sweeping sorted starts against sorted ends.