Python, heapq solutions with explanation


  • 6
    O

    Firstly, we sort the intervals with its start time. Then, image each room to be a "bucket," whether or not you can put a new "interval" into the bucket depends on the end time of latest interval (new_interval.begin >= some_room.latestEventEndingTime).

    But, if there are multiple rooms that could fit, which one should we choose?

    The answer is you should choose the room with earliest ending time, so that you can put all the intervals into rooms as concise as you can! Then you can get the minimum room you need!

    So the direct implementation would be keep a heap to store every room's latest event ending time.
    And every time you just pop out the minimum value in the heap, and replace with the new event's ending time.

    When the earliest ending time is later than the new event's begin time, you know that you will need a new room!

        if not intervals:
            return 0
        intervals.sort(key = lambda x: x.start)
        rooms, maxRoomNeed = [], 1
        heapq.heappush(rooms, intervals[0].end)
        for i in range(1, len(intervals)):
            if intervals[i].start >= rooms[0]:
                heapq.heappushpop(rooms, intervals[i].end)
            else:
                heapq.heappush(rooms, intervals[i].end)
                maxRoomNeed = max(maxRoomNeed, len(rooms))
        return maxRoomNeed

Log in to reply
 

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