Meeting Rooms II

The number of rooms needed is the maximum number of meetings happening at the same time. For every meeting’s start time, count how many other meetings are in progress at that instant; the answer is the largest such count.

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        max_rooms = 0
        for s1, e1 in intervals:
            concurrent = 0
            for s2, e2 in intervals:
                if s2 <= s1 < e2:
                    concurrent += 1
            max_rooms = max(max_rooms, concurrent)
        return max_rooms

This checks every pair of meetings — O(n²) time — and misses the fact that sorting the start and end times lets us sweep through time in one pass.

Sort meetings by start time. Keep a min-heap holding the end time of every meeting currently occupying a room — the top of the heap is always the room that frees up soonest. For each meeting (in start order): if the earliest-freeing room’s end time is at or before this meeting’s start, that room is free, so pop it and reuse it; otherwise no room is free and a new one is pushed. Push the current meeting’s end time either way. The number of rooms in use at any point is the heap’s size, so the answer is the largest size the heap ever reaches.

import heapq

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda iv: iv[0])
        heap = [intervals[0][1]]  # end times of occupied rooms
        for start, end in intervals[1:]:
            if heap[0] <= start:
                heapq.heappop(heap)  # earliest room just freed up, reuse it
            heapq.heappush(heap, end)
        return len(heap)

Tracing intervals = [[0,30],[5,10],[15,20]] (already sorted by start). Watch the soonest-freeing room decide each meeting: if its end time is at or before the new start, reuse that room; otherwise open a new one.

The heap’s size peaked at 2, so 2 rooms are required.

Complexity: sorting costs O(n log n), and each of the n meetings does one heap push/pop (O(log n)) → O(n log n) time; the heap holds up to n end times → O(n) space.