LC253 Meeting Rooms II

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        """
        # main idea: priority queue/ min heap, with key being ending time of meeting. 
        tc O(NlgN)   sc  O(N)
        stack 
        1. sort by start
        2. iterate interv,using minPQ, keep appending end time, remove invalid end time according to current start time   
        3. return minPQ size 
        """
        intervals.sort(key=lambda x: x[0])
        pq = []
        for s,e in intervals:
            # there is one room empty out so we can assign current meetting in there 
            if pq and pq[0] <= s: # why not use while ???  because we need to keep record of max rooms that were using at the same time 
                heappop(pq)
            heappush(pq,e)
        return len(pq)

# time O(NlgN) space O(2N)
   class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        """
        # main idea: treat start and end time seperately, convert meeting interv ==> time point.  keep increment rooms when there is a new start time. but we will decrese by one room when there is end time complete
        """
        begin,end = [],[]
        for s,e in intervals:
            begin.append(s)
            end.append(e)
        begin.sort()
        end.sort()
        
        rooms = 0
        p_end = 0
        for i in range(len(begin)):
            if begin[i] >= end[p_end]:
                rooms -= 1
                p_end += 1
            rooms += 1
        return rooms