Meeting Rooms II

IntervalsHeapsSorting

25 min

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.

Example

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]

Initial Intervals:

[0, 30]

[5, 10]

[15, 20]

Minimum Rooms Required:

Output: 2

Solution

This problem can be solved efficiently using a min-heap to keep track of the end times of meetings currently in progress.

Algorithm Steps

Sort the intervals by their start times.
Initialize a min-heap and add the end time of the first meeting.
Iterate through the remaining intervals. If the current meeting's start time is after or at the same time as the earliest ending meeting in the heap, a room is free. Pop from the heap.
Push the current meeting's end time to the heap.
The maximum size the heap reaches is the minimum number of rooms required.

Intervals

[0, 30]

[5, 10]

[15, 20]

Heap (End Times)

Rooms: 0

Start with the unsorted intervals.

Meeting Rooms II Solution


import heapq

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[0])
        
        # Min-heap to store end times of meetings
        end_times = [intervals[0][1]]
        
        for i in range(1, len(intervals)):
            # If the current meeting starts after the earliest-ending meeting finishes
            if intervals[i][0] >= end_times[0]:
                heapq.heappop(end_times)
            
            heapq.heappush(end_times, intervals[i][1])
            
        return len(end_times)