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)

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment