# 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.
Given [[0, 30],[5, 10],[15, 20]], return 2.
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:
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:
# Code (Python)
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 >= ongoing: heapq.heappop(ongoing) heapq.heappush(ongoing, meeting) num_rooms = max(num_rooms, len(ongoing)) return num_rooms
import itertools def num_rooms(meetings): timeline = sorted(itertools.chain(((meeting, 1) for meeting in meetings), ((meeting, -1) for meeting in meetings))) # chaining two streams rooms, max_rooms = 0, 0 for time in timeline: rooms += time max_rooms = max(max_rooms, rooms) return max_rooms
# Code (C++)