Description

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.

Example 1:

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

Solution

首先按照开始time进行排序，保持最小堆存end time, 如果当前最早结束的会议晚于当前要开始的会议，push heap(多一间房) ，else 先pop再push

Time O(NlogN)
Space O(N)

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""
import heapq
class Solution:
    """
    @param intervals: an array of meeting time intervals
    @return: the minimum number of conference rooms required
    """
    def minMeetingRooms(self, intervals):
        # Write your code here
        s_inter = sorted(intervals,key= lambda x: x.start)
        inter_heap = [s_inter[0].end]
        
        for s in s_inter[1:]:
            if s.start < inter_heap[0]:
                heapq.heappush(inter_heap,s.end)
            else:
                heapq.heappop(inter_heap)
                heapq.heappush(inter_heap,s.end)
                
                
        return len(inter_heap)

           ```