Python use priority queue O(nlogn)


  • 4
    Y

    Sort the intervals according to their start time, then count how many meetings are still going when a new meeting starts.

    from heapq import *
    class Solution(object):
        def minMeetingRooms(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: int
            """
            intervals.sort(key=lambda i:i.start)
            pq=[]
            res=0
            for i in intervals:
                """
                pop meetings already end
                """
                while pq and pq[0]<=i.start:
                    heappop(pq)
                heappush(pq,i.end)
                res=max(res,len(pq))
            return res

  • 0

    Nice, although I don't see why you push (i.end,i) instead of just i.end.


  • 0
    Y

    Thank you for your comment! You are right, push i.end is enough!


Log in to reply
 

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