When meetings collide you need parallel rooms. The minimum number of rooms equals the maximum number of meetings running at the same instant.
Implement min_meeting_rooms(meetings). Sort all start times and all end times independently, then sweep with two pointers. Each time the next start comes before the next end, a new meeting begins and needs a room; otherwise a meeting has ended and frees one. Track the peak concurrent count.
A room frees up the instant a meeting ends, so a start equal to an end can reuse the room. Return 0 for no meetings.
def merge_intervals(intervals):
if not intervals:
return []
ordered = sorted(intervals, key=lambda pair: pair[0])
merged = [list(ordered[0])]
for start, end in ordered[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
def insert_interval(intervals, new):
result = []
start, end = new[0], new[1]
i, n = 0, len(intervals)
while i < n and intervals[i][1] < start:
result.append(list(intervals[i]))
i += 1
while i < n and intervals[i][0] <= end:
start = min(start, intervals[i][0])
end = max(end, intervals[i][1])
i += 1
result.append([start, end])
while i < n:
result.append(list(intervals[i]))
i += 1
return result
def can_attend_all(meetings):
ordered = sorted(meetings, key=lambda pair: pair[0])
for i in range(1, len(ordered)):
if ordered[i][0] < ordered[i - 1][1]:
return False
return True
def min_meeting_rooms(meetings):
"""Return the minimum number of rooms to hold all meetings.
meetings is a list of [start, end] pairs. A room can host another
meeting the instant one ends. Sort the start times and end times,
then sweep to track how many meetings run at once.
"""
# TODO: sort starts and ends, sweep with two pointers, track the peak
passThe editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
When meetings collide you need parallel rooms. The minimum number of rooms equals the maximum number of meetings running at the same instant.
Implement min_meeting_rooms(meetings). Sort all start times and all end times independently, then sweep with two pointers. Each time the next start comes before the next end, a new meeting begins and needs a room; otherwise a meeting has ended and frees one. Track the peak concurrent count.
A room frees up the instant a meeting ends, so a start equal to an end can reuse the room. Return 0 for no meetings.
Press Run Tests or ⌘↩ to check your solution.