Meeting Rooms II – Solution & Complexity

• 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.

• 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.

• 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.

The sorted start/end sweep counts exactly how many concurrent meetings are ever needed at once.

• 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.