unreasonably effective

link

We schedule meetings in order of their start times. If there is a free room, we use it or we declare a new room is required.

Say we are trying to schedule the -th meeting and currently there are meeting rooms with earlier meetings scheduled. Which among these rooms would be the most likely to be free? The one whose meeting ends the earliest. If that room is still occupied, the rest of the rooms must be occupied as well. So, as we schedule meetings, we keep them in a min-heap with end-time as the key. If we can re-use the earliest ending meeting’s room the min-heap does not grow. In the end, the size of the heap is the number of required rooms.

Time: , space: .

from heapq import heappush as push, heappop as pop

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        minq = []
        for start, end in intervals:
            if minq and start >= minq[0]:
                pop(minq)
            push(minq, end)
        
        return len(minq)