Leetcode: Meeting Rooms 2

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] find the minimum number of conference rooms required.

Example

Notice how we need 4 meeting rooms because a maximum number of 4 intervals overlap even though there are more than a total of four overlapping intervals.

Approach

The idea is to count the maximum number of overlapping intervals. First, sort the intervals in order of finishing time. O(n lg n) Second, maintain a min heap of intervals sorted by finishing time (earliest finishing time is at the top). This min heap represents the meeting rooms. Process each interval. At each interval, if the current interval starts after the last interval scheduled finishes, then we can replace that interval with the current interval. Otherwise, we must allocate another room.