253. Meeting Rooms II.md

253. Meeting Rooms II

Algorithm 1 Better

• similar to the meeting room question
• add (start time,1) and (end time, -1) to a list
• sort the list by first and second entry of each point.
• using a count, and loop through the whole point list, add 1 if started and reduce 1 if ended. keep track of the max count in the whole process and return the max.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        pointList = []
        maxRoom = 0
        count = 0
        for onePoint in intervals:
            pointList.append((onePoint[0], 1))
            pointList.append((onePoint[1], -1))
        pointList.sort(key=lambda x:(x[0], x[1]))
        print(pointList)
        for onePoint in pointList:
            count += onePoint[1]
            maxRoom = max(maxRoom, count)
        return maxRoom

ALgorithm 2 Heapq

• by using a heap to sort the room by end time
• sort the interval first.
• loop through all intervals and compare the new start time with the end time in the heap one by one. from early end time to late end time.
• only need to push end time to the heap.BrokenPipeError
• if the new start time overlap with the any of the end time, push it to the heap
• otherwise dont push it.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        roomHeap = []
        # sort based on start time
        intervals.sort(key = lambda x:x[0])
        # push the first end time
        heapq.heappush(roomHeap, intervals[0][1])
        
        for point in intervals[1:]:
            # if start time is later than end time
            if point[0] >= roomHeap[0]:
                heapq.heappop(roomHeap)
            # in both case, pop new end time to the heap
            heapq.heappush(roomHeap, point[1])
        return len(roomHeap)
        

Algorithm 3

• build a start array and an end array
• use a roomCount and a currentEnd
• go through every start, if start < end, roomCount ++. if start >= end means one room is done, currentEnd ++.

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        starts = []
        ends = []
        for point in intervals:
            starts.append(point[0])
            ends.append(point[1])
        
        starts.sort()
        ends.sort()
        curEnd = 0
        numRoom = 0
        for oneStart in starts:
            if oneStart < ends[curEnd]:
                numRoom += 1
            else:
                curEnd += 1
        return numRoom