Meeting Rooms II

题目描述

解题方法

用一个min heap记录之前的meeting的结束时间，如果结束时间在当前meeting start 之前，就可以减少一个room了。

Solution

from operator import attrgetter
from heapq import *
# 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
        """
        length = len(intervals)
        if length < 1:
            return 0
        intervals.sort(key=attrgetter("start"))    

        max_rooms = 0
        result = 0
        heap = []

        for i in range(length):
            result += 1
            while heap and heap[0] <= intervals[i].start:
                heappop(heap)
                result -= 1
            max_rooms = max(max_rooms, result)
            heappush(heap, intervals[i].end)

        return max_rooms

Reference