Meeting Rooms II – Solution & Complexity
Watch: Meeting Rooms II by sorting starts and ends
The rooms you need equal the most meetings running at the same moment. Sort the start times and the end times separately, then walk the starts: if the next start is before the earliest unused end, open a room; otherwise that meeting has ended, so reuse its room and move to the next end. A meeting ending at 11 and one starting at 11 don't clash, so compare with start ≥ end. O(n log n) time, O(n) space.
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.