# 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: