Meeting Rooms II

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of meeting rooms required to schedule all meetings without any conflicts.

Note: (0,8),(8,10) is not considered a conflict at 8.

room1: (0,40)
room2: (5,10),(15,20)

Approach

Sort meetings by start time and use a min-heap of end times. For each meeting, if the earliest ending meeting ends before the current starts, reuse that room (pop); otherwise allocate a new room. The heap size is the rooms in use.

Why It Works

The min-heap tracks the earliest ending room. Reusing it when possible minimizes room count, and any overlap forces a new room. The maximum heap size during the scan equals the minimum rooms required.

Complexity

• Time: O(n log n)
• Space: O(n)

Reference Implementation (Python)

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap = []
        for start, end in intervals:
            if heap and start >= heap[0]:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
        return len(heap)