No need of priority queue, just one loop

  • 7
    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.