# 253. Meeting Rooms II
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei)
, find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
# Solution
Approach 1: keep all ongoing meetings in a min heap. For each new incoming meeting, see if there are ongoing meetings that ends before it starts. Time: O(NlogN)
.
Approach 2: map each interval on to the timeline -- +1 room for meeting start, -1 for meeting end, then go through the timeline to count the max room required. Time: O(NlogN)
.
# Code (Python)
Approach 1:
import heapq
def num_rooms(meetings):
ongoing = [] # all ongoing meetings (just store the end_time)
meetings = sorted(meetings)
num_rooms = 0
for meeting in meetings:
# while the next meeting's start time >= the earliest ending meeting among the ongoing meetings, finish those meetings first
while ongoing and meeting[0] >= ongoing[0]:
heapq.heappop(ongoing)
heapq.heappush(ongoing, meeting[1])
num_rooms = max(num_rooms, len(ongoing))
return num_rooms
Approach 2:
import itertools
def num_rooms(meetings):
timeline = sorted(itertools.chain(((meeting[0], 1) for meeting in meetings), ((meeting[1], -1) for meeting in meetings))) # chaining two streams
rooms, max_rooms = 0, 0
for time in timeline:
rooms += time[1]
max_rooms = max(max_rooms, rooms)
return max_rooms
# Code (C++)
Approach 1:
Approach 2: