Medium

Meeting Rooms II

LAB

Given meeting intervals, return the minimum number of rooms required.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      0,
      30
    ],
    [
      5,
      10
    ],
    [
      15,
      20
    ]
  ]
}

Output
2

FUNCTION SHAPE

intervals: intMatrix→int

SOLUTION NOTE

Basically we maintain a min heap of earliest current active meeting end times. If this meeting start time is after the earliest meeting end, that means that meeting is done and we can remove it from the heap. Otherwise, we want to add this meeting as currently active. At the end, the number of currently active meetings is the answer.

Note: we can solve Meetings Room I using this algorithm, and checking if the minMeetingRooms == 1.

Reveal reference solution +

pythonREFERENCE

# Heap solution
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    heap = []  # min heap of end times
    for a, b in sorted(intervals):
        if heap and a >= heap[0]: heappop(heap)
        heappush(heap, b)
    return len(heap)

# Line sweep solution
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    lines = defaultdict(int)
    for a, b in intervals:
        lines[a] += 1
        lines[b] -= 1
    res = 0
    acc = 0
    for s in sorted(lines):
        acc += lines[s]
        res = max(res, acc)
    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗