unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 2402: Meeting Rooms III

link

Looking at the scheduling requirements:

  1. Each meeting will take place in the unused room with the lowest number.
    • We keep a min heap of available rooms.
  2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
    • We keep (meeting-end-time, room-number) in a min heap. If the top meeting is still on-going, all other meetings are on-going as well. If no rooms are available to schedule a meeting, we delay the meeting until the end-time of the top meeting. Since the heap’s secondary key is room number, a tie in end-time is broken in favor of a room with lower number.
  3. When a room becomes unused, meetings that have an earlier original start time should be given the room.
    • We schedule meeting in order of their start times.

Say there are m meetings.

Time: \mathcal{O}(m \cdot \lg{m} + m \cdot \lg{n}), space: \mathcal{O}(\lg{m} + n).

from heapq import heapify, heappush as push, heappop as pop

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        booking = [0] * n
        meetings.sort()

        meeting_q = []
        room_q = [room for room in range(n)]
        heapify(room_q)

        for start, end in meetings:
            while meeting_q and start >= meeting_q[0][0]:
                _, available_room = pop(meeting_q)
                push(room_q, available_room)
            if room_q:
                used_room = pop(room_q)
                booking[used_room] += 1
                push(meeting_q, (end, used_room))
                continue

            earliest_end, used_room = pop(meeting_q)
            duration = end-start
            delayed_start = earliest_end
            delayed_end = delayed_start + duration
            booking[used_room] += 1
            push(meeting_q, (delayed_end, used_room))

        return booking.index(max(booking))

tanvirdotzaman

,

Leave a comment