Meeting Rooms II

Find the smallest number of rooms needed for all meetings.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Meeting Rooms II: Before each start, pop every ended meeting; then push the new end and record the largest heap size.

Input and goalFind the smallest number of rooms needed for all meetings.

Initialize the active heapMeetings are sorted by start as [0,30], [5,10], [5,15], [20,25]. end_times is empty and most_rooms=0.

root -minimum-left -right -

exampleintervals = [[0,30], [5,10], [5,15], [20,25]]heapArray[]heapMeaningroot above its children; active meeting end timesnextMeeting[0,30]mostRooms0

Recognize it

The question asks for the maximum number of simultaneous intervals, and meetings that end before the next start release reusable capacity.

Keep true

Immediately before pushing a meeting, the heap contains exactly the end times greater than its start; after pushing, heap size equals active rooms and most_rooms is the largest size seen.

Reuse it

For capacity over time, sweep arrivals and keep active expirations ordered by the next one to finish; this transfers to server concurrency, platform usage, and resource reservation.

Pattern: Sort starts and keep active end times in a heap.

Simple idea: Before starting a meeting, remove every meeting that already ended. Add the new end time. The largest active heap size is the room count.

import heapq

def min_meeting_rooms(intervals: list[list[int]]) -> int:
   end_times: list[int] = []
   most_rooms = 0

   for start, end in sorted(intervals):
      while end_times and end_times[0] <= start:
         heapq.heappop(end_times)
      heapq.heappush(end_times, end)
      most_rooms = max(most_rooms, len(end_times))
   return most_rooms

Cost: $O(n\log n)$ time and $O(n)$ space.