48 lines
1.4 KiB
Python
48 lines
1.4 KiB
Python
"""Minimum meeting rooms.
|
|
|
|
Given a list of intervals [start, end) (half-open), return the minimum
|
|
number of concurrent "rooms" needed so no two overlapping intervals share
|
|
a room. Touching endpoints (end == start) do NOT overlap.
|
|
|
|
Approach: sweep-line over events. A start at time t needs a room before an
|
|
end at the same time t frees one, so process ends before starts at equal t.
|
|
O(n log n) time, O(n) space.
|
|
|
|
Also provided: min_rooms_heap(intervals) using a min-heap of end times, for
|
|
cross-checking.
|
|
"""
|
|
from __future__ import annotations
|
|
import heapq
|
|
|
|
|
|
def min_meeting_rooms(intervals):
|
|
"""Return minimum rooms needed for intervals [(s,e), ...]."""
|
|
events = []
|
|
for s, e in intervals:
|
|
if e < s:
|
|
raise ValueError("end < start: %r" % ((s, e),))
|
|
if s == e:
|
|
continue # empty half-open interval
|
|
events.append((s, 1)) # start
|
|
events.append((e, -1)) # end
|
|
# sort by time; at equal time, ends (-1) before starts (+1)
|
|
events.sort(key=lambda x: (x[0], x[1]))
|
|
cur = 0
|
|
best = 0
|
|
for _, delta in events:
|
|
cur += delta
|
|
if cur > best:
|
|
best = cur
|
|
return best
|
|
|
|
|
|
def min_rooms_heap(intervals):
|
|
ends = []
|
|
for s, e in sorted(intervals):
|
|
if s >= e:
|
|
continue # empty half-open interval needs no room
|
|
if ends and ends[0] <= s:
|
|
heapq.heapreplace(ends, e)
|
|
else:
|
|
heapq.heappush(ends, e)
|
|
return len(ends) |