Meeting rooms II: min-heap of current end times

Coding Challenges
, ,
1

Problem. Given meeting intervals, return the minimum number of rooms needed so that every meeting can happen without conflict.

This is the classic sweep-line with active-room heap pattern.

Examples:

  • intervals = [[0,30],[5,10],[15,20]] → 2
  • intervals = [[7,10],[2,4]] → 1
  • intervals = [[1,5],[2,3],[4,6]] → 2

Solution. Sort meetings by start time. Keep a min-heap of end times for rooms currently in use. If the earliest-ending room is free before the next meeting starts, reuse it; otherwise allocate a new room.

import heapq


def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda interval: interval[0])
    room_ends = []

    for start, end in intervals:
        if room_ends and room_ends[0] <= start:
            heapq.heapreplace(room_ends, end)
        else:
            heapq.heappush(room_ends, end)

    return len(room_ends)

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

Gotchas.

  • The heap stores end times, not full intervals.
  • A room becomes reusable when its end time is less than or equal to the next start.
  • If you need the maximum overlap only, a sweep over separate sorted starts and ends is another common solution.

Run: Meeting Rooms Ii