No need of priority queue, just one loop


  • 7
    D
    class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        
        points = []
        for point in intervals:
            points.append((point.start, 1))
            points.append((point.end, 0))
        
        points.sort(key=lambda x:(x[0],x[1]))
        
        res = 0
        cur = 0
        for val,typ in points:
            cur = cur+1 if typ == 1 else cur-1
            res = max(res, cur)
        
        return res
    

    Cur is the maximum line if we draw a vertical line in time point.

    minus 1 when meet the begin point, add 1 when meet the end point.

    traverse and record the maximum number


Log in to reply
 

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