Interval Grouping¶

Table of Contents¶

2406. Divide Intervals Into Minimum Number of Groups (Medium)
253. Meeting Rooms II (Medium) 👑

2406. Divide Intervals Into Minimum Number of Groups¶

LeetCode | 力扣
Tags: Array, Two Pointers, Greedy, Sorting, Heap Priority Queue, Prefix Sum

253. Meeting Rooms II 👑¶

LeetCode | 力扣
Tags: Array, Two Pointers, Greedy, Sorting, Heap Priority Queue, Prefix Sum

Python

"""
- Given an array of meeting time `intervals` where `intervals[i] = [start_i, end_i]`, return the minimum number of conference rooms required.
"""

import heapq
from typing import List


# Heap
def minMeetingRooms(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])
    minHeap = [intervals[0][1]]

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

    return len(minHeap)


if __name__ == "__main__":
    intervals = [[0, 30], [5, 10], [15, 20]]
    assert minMeetingRooms(intervals) == 2