leetcode-greedy

253. Meeting Rooms II.py

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        """
        There're two major portions that take up time.
        One is sorting part, we sort the intervals based on starting time, which takes O(nlogn) time.

        Another one is we use min-heap. We have N operations of insertion or extraction totally. It takes O(n * log(n)) time.

        T: O(nlogn)
        S: O(n) because in the worse case, we might contains N elements in min-heap

        """
        n = len(intervals)
        if n == 0:
            return 0

        heap = []  # stores the end time of intervals
        for i in sorted(intervals, key=lambda x:x[0]):
            starting_time, ending_time = i[0], i[1]
            # sorted the meeting time rooms based on starting time.
            if heap and starting_time >= heap[0]: 
                # means two intervals can use the same room
                heapq.heapreplace(heap, ending_time)
            else:
                # a new room is allocated
                heapq.heappush(heap, ending_time)
        return len(heap)