LeetCode 253: Meeting Rooms Ii — Step-by-Step Visual Trace

#python #algorithms #leetcode

Medium — Heap | Greedy | Sorting | Intervals

The Problem

Given a list of meeting time intervals, determine the minimum number of meeting rooms required to schedule all meetings without conflicts.

Approach

Sort meetings by start time, then use a min-heap to track end times of ongoing meetings. For each meeting, remove finished meetings from the heap and add the current meeting's end time. The heap size represents active meetings requiring rooms.

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

Code

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 = []
        heapq.heappush(min_heap, intervals[0][1])

        for i in range(1, len(intervals)):
            if intervals[i][0] >= min_heap[0]:
                heapq.heappop(min_heap)
            heapq.heappush(min_heap, intervals[i][1])

        return len(min_heap)