Meeting Rooms II

Intuition

Sort the meetings by when they start, then walk through them while keeping a min-heap of the end times of meetings that currently occupy rooms. For each new meeting, if the room that frees up soonest (the smallest end time on the heap) is already done by this meeting's start, we reuse it by popping that end time. Either way we push the current meeting's end time. The heap's size at any moment equals the number of rooms in use, and its peak size is the answer.

Algorithm walkthrough

1. 1Sort the intervals by start time.
2. 2Create an empty min-heap that will store the end times of active meetings.
3. 3For each meeting, if the heap is non-empty and its smallest end time is at or before this meeting's start, pop it because that room is now free.
4. 4Push the current meeting's end time onto the heap.
5. 5After processing everything, the number of elements remaining on the heap is the maximum concurrency, which equals the rooms needed.

Implementation

import heapq

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 heap[0] <= start:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
        return len(heap)

Intuition

Overlap only cares about how many meetings are running at once, not which meeting is which. So pull all start times into one sorted list and all end times into another. Sweep through the starts; before admitting each start, release every room whose end time has already passed. The running count of occupied rooms rises with each start and falls with each end, and its highest value during the sweep is the number of rooms required.

Algorithm walkthrough

1. 1Extract every start time into one array and every end time into another.
2. 2Sort both arrays independently.
3. 3Walk through the starts with a pointer j into the ends array, both beginning at zero.
4. 4Before counting a new start, advance j past every end time that is at or before that start, decrementing the active-room count for each.
5. 5Increment the count for the current start and track the maximum count seen; that maximum is the answer.

Implementation

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 = 0
        max_rooms = 0
        j = 0
        for start in starts:
            while j < len(ends) and ends[j] <= start:
                rooms -= 1
                j += 1
            rooms += 1
            max_rooms = max(max_rooms, rooms)
        return max_rooms