4.27.5 — Meeting Rooms II

LeetCode 253 · Medium

The problem

Return the minimum number of rooms needed so that every meeting can happen.

[[0,30],[5,10],[15,20]]   →  2
[[7,10],[2,4]]            →  1

The pattern

The answer is the largest number of meetings happening at the same moment. You need one room per concurrent meeting, and no more, because a room is reusable the instant a meeting ends.

So the question becomes: what is the maximum overlap at any point in time?

Two standard answers, and both are worth knowing.

Solution 1 — the sweep line

Forget which start belongs to which end. Treat starts and ends as separate events, sort all of them by time, and sweep:

• a start adds one to the count of rooms in use;
• an end subtracts one.

The answer is the highest the count ever reaches.

Python

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = sorted(i[0] for i in intervals)
        ends = sorted(i[1] for i in intervals)

        rooms = best = 0
        s = e = 0

        while s < len(starts):
            if starts[s] < ends[e]:          # a meeting begins before any ends
                rooms += 1
                s += 1
                best = max(best, rooms)
            else:                            # a meeting ends first — free a room
                rooms -= 1
                e += 1

        return best

TypeScript

function minMeetingRooms(intervals: number[][]): number {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, best = 0, s = 0, e = 0;

  while (s < starts.length) {
    if (starts[s] < ends[e]) { rooms++; s++; best = Math.max(best, rooms); }
    else { rooms--; e++; }
  }

  return best;
}

Separating the starts from the ends is the move. It looks wrong — you have thrown away which end belongs to which start — but it does not matter. You are only counting how many meetings are open at each moment, and for that the pairing is irrelevant.

starts[s] < ends[e] uses <, so a meeting ending exactly when another starts frees the room in time. That is the same convention as 4.27.4.

The loop runs while starts remain. Once every meeting has begun, the count can only fall, so the maximum has already been seen.

O(n \log n) time, O(n) space.

Solution 2 — a min-heap of end times

Sort the meetings by start. Keep a min-heap of the end times of the meetings currently in rooms.

For each meeting: if the earliest-ending meeting has already finished, reuse its room by popping it. Then push this meeting's end. The heap's size is the number of rooms in use, and its maximum is the answer.

import heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        heap = []                                  # end times of busy rooms

        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)                # that room is free again
            heapq.heappush(heap, end)

        return len(heap)

Only one pop per meeting is needed, even if several rooms have freed up. If two rooms are free you only need one for this meeting, and the other stays available for later — the heap's size is still correct.

The final heap size is the answer, because the heap only ever shrinks when a room is genuinely reused, so its peak equals its final size.

O(n \log n) time, O(n) space.

Which to write

The heap version reads more like the story — rooms with meetings in them — and it extends when you need to know which room each meeting used, since you can store room identifiers alongside the end times.

The sweep line is slightly faster and generalises further, and it is the one to reach for when the question is about counts rather than assignments.

Say both, pick one, and say why.

The sweep line, generalised

This is the idea worth taking away from the whole chapter.

Convert each interval into two events, sort all events by time, and sweep with a running count.

events = []
for start, end in intervals:
    events.append((start, +1))
    events.append((end, -1))
events.sort()          # ties: -1 before +1, so an ending frees a room first

The tie-break matters. At equal times you want the -1 processed first, so a meeting ending at 10 frees a room for one starting at 10. Sorting tuples does this automatically because -1 < +1.

It solves a large family:

• Maximum concurrent anything — meetings, downloads, database connections, aircraft in a sector.
• Car Pooling (LeetCode 1094) — passengers boarding and leaving, with a capacity check.
• My Calendar II and III — counting double and triple bookings.
• The skyline problem (LeetCode 218) — a sweep line with a heap of building heights.
• Rate limiting and capacity planning in production systems, which is Chapter 11.3.

Complexity

O(n \log n) time and O(n) space for both solutions.

If the times were small bounded integers, you could use a difference array instead: add 1 at each start, subtract 1 at each end, then take a prefix sum and find its maximum. O(n + T) where T is the time range. That is the bounded-values trick from 4.4.5, and it is worth naming as the optimisation when times are, say, minutes in a day.

What the interviewer will push on

"Why can you separate starts from ends?" You are counting concurrency, and the pairing does not affect the count.

"What happens at equal times?" An end must be processed before a start, or a reusable room is missed.

"Why is the heap's size the answer?" It holds exactly the meetings currently occupying rooms.

"Why only one pop per meeting?" You only need one room for one meeting.

"What if you needed to know which room each meeting used?" Store room ids in the heap alongside the end times.

"What if the times were minutes in a day?" A difference array, O(n + 1440).

One thing to volunteer: name the sweep line and give one non-meeting use of it. It is the most transferable technique in the interval chapter, and interviewers notice when a candidate has a name for what they are doing.

Next: 4.27.6 Minimum Interval to Include Each Query — the hardest interval problem, combining sorting, a heap and offline query processing.