Meeting Rooms II – Solution & Complexity
Solution Walkthrough
Step 1: Restate the scheduling goal
- You do not need to decide which room gets which meeting yet; you only need the largest number of overlapping meetings at any time.
- If three meetings overlap at one instant, three rooms are unavoidable. If at most two overlap, two rooms are enough.
Step 2: Brute-force baseline
- For every meeting, compare it with every other meeting and try to count how many intervals overlap at each start time.
- That direct approach is easy to reason about, but it costs
O(n^2)and is too slow for large schedules.
Step 3: Sort starts and ends separately
- Put every start time in one array and every end time in another, then sort both.
- Walk through starts from earliest to latest while also tracking the earliest room that becomes free.
- If the next start is strictly earlier than the earliest end, no room is free yet, so you need a new room. Otherwise one room can be reused and you advance the end pointer.
Step 4: Final solution (all languages)
The sorted start/end sweep counts exactly how many concurrent meetings are ever needed at once.
Step 5: Why the sweep works
- Every start either consumes a brand-new room or reuses the earliest room that already finished.
- Using the earliest end is safe because any later-ending room is even less available.
- A min-heap of active end times solves the same problem and is a good way to extend this into actual room assignment.
