My python solution - using min heap


  • 0
    S
    # 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
            """
            
            class myInterval(object):
                # needed for heapq, heap to order based on end times
                # which ever ends early should be popped
                def __init__(self,interval):
                    self.start = interval.start
                    self.end   = interval.end
                
                def __cmp__(self,other):
                    return cmp(self.end,other.end)
                
                def __lt__(self,other):
                    return self.end < other.end
                
            
            def overlap(i1,i2):
                if i1.end <= i2.start or i2.end <= i1.start:
                    # i2 starts after i1 ends
                    # i1 starts after i2 ends
                    return False
                return True
            
            
            heap = []
            ans  = 0
            
            # sort by start times, one that starts early will be queued first
            intervals.sort(key=lambda x:x.start)
            for interval in intervals:
                x = myInterval(interval)
                while heap and not overlap(x,heap[0]): 
                    # if the one that ends early is not overlapping with meeting request
                    # free room for new meeting request
                    heapq.heappop(heap)
                # push new request
                heapq.heappush(heap, x )
                # max number of requests at any given time, is minimum number of rooms needed
                ans = max(ans,len(heap))
            
            return ans

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.