253. Meeting Rooms II

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        # Heap 初始化
        free_rooms = []

        # 将输入的list按照升序排序
        intervals.sort(key=lambda x: x.start)

        # Add the first meeting
        heapq.heappush(free_rooms, intervals[0].end)

        # Go though all remaining meetings
        for i in range(1, len(intervals)):
            # 重点就在于heap的第一个值heap[0]上，因为heap的性质，heap[0]是最小的值。

            if free_rooms[0] <= intervals[i].start:
                # 所以当heap[0]也就是最早结束时间的room <= 下一个meeting的开始时间。
                # 就把heap[0] 移除，然后插入新的interval。

                heapq.heapreplace(free_rooms, intervals[i].end)

            else:
                # 当heap[0] > 下一个meeting的开始时间，就直接插入新的room

                heapq.heappush(free_rooms, intervals[i].end)


        return len(free_rooms)