Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

 

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

 

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

 

Ideas:  

1. 先sort intervals，然后将meeting 按照start time 来排列

2. 建一个以end time 为element的min heap

3. 每次对于每个interval， 看start time >= min heap[0](最早结束的meeting)， 表明有房间空出来， 那么heapq.heappop(free_rooms)

4. 再heapq.heappush(free_rooms, endtime)

5. 将所有会议都review一遍之后还在heap里面的就是需要的房间的数量

Code

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[0])
        free_rooms = []
        for s, e in intervals:
            if free_rooms and s >= free_rooms[0]:
                heapq.heappop(free_rooms)
            heapq.heappush(free_rooms, e)
        return len(free_rooms)