Python solution with detailed explanation


  • 0
    G

    Solution

    Meeting Rooms II https://leetcode.com/problems/meeting-rooms-ii/

    • Use an event based simulation method. There are two events: start and end of a meeting.
    • Use a heap to drive the event based simulation.
    • Add all events to a min-heap. Then extract the minimum event. For start of a meeting, increment curr_room count by 1. For end of meeting, reduce curr_room count by 1. At each iteration, update the maximum running count for curr_rooms.
    • Time complexity: O(N * lg (N)). Space complexity: O(N).
    from heapq import heappush, heappop
    class Solution(object):
        def minMeetingRooms(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: int
            """
            heap = []
            for interval in intervals:
                heappush(heap, (interval.start, "s"))
                heappush(heap, (interval.end, "e"))
            min_conference_rooms, curr_rooms = 0, 0
            while heap:
                tm, ev_id = heappop(heap)
                curr_rooms = curr_rooms + 1 if ev_id == "s" else curr_rooms - 1
                min_conference_rooms = max(min_conference_rooms, curr_rooms)
            return min_conference_rooms
    

Log in to reply
 

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