Leetcode 2402. Meeting Rooms III

Let's understand what we're being asked to do. We have meetings with start times and durations, and a fixed number of rooms. Each meeting must be assigned to a room, but if all rooms are busy, the meeting gets delayed (keeping its duration) until a room becomes available.

For example, with 2 rooms and meetings [[0,10], [1,5], [2,7]]:

• Meeting 0 starts at time 0, duration 10 → assigned to room 0 (ends at time 10)
• Meeting 1 starts at time 1, duration 5 → assigned to room 1 (ends at time 6)
• Meeting 2 starts at time 2, duration 7 → both rooms busy! Room 1 frees first at time 6, so meeting 2 is delayed to start at time 6 (ends at time 13)

Important constraint: Meetings are processed in order of their original start times (earliest first). If a meeting is delayed, it keeps its duration but starts when a room becomes available.

Key question: Which room hosted the most meetings? We need to count assignments per room and return the index of the room with the maximum count (if tied, return the lowest-numbered room).

Edge cases: What if all meetings fit without delays? What if one room is always chosen (lowest-numbered available)? What if multiple rooms tie for most meetings?

For each meeting, scan through all rooms linearly to find the earliest available one. Track each room's next free time in an array. For each meeting, iterate through all rooms to find the one with the minimum free time (or the lowest index if multiple are free now). Update that room's free time and increment its meeting count. This approach is simple but inefficient because we repeatedly scan all rooms.

def most_booked_room(n, meetings):
    """
    Brute force approach: For each meeting, scan all rooms linearly
    to find the earliest available one.
    """
    # Sort meetings by start time
    meetings.sort(key=lambda x: x[0])
    
    # Track next free time for each room
    room_free_time = [0] * n
    # Count meetings per room
    meeting_count = [0] * n
    
    # Process each meeting
    for meeting in meetings:
        start, end = meeting[0], meeting[1]
        duration = end - start
        
        # Scan all rooms to find earliest available
        best_room = -1
        earliest_free = float('inf')
        
        for room_idx in range(n):
            # Check if this room is better
            if room_free_time[room_idx] < earliest_free:
                earliest_free = room_free_time[room_idx]
                best_room = room_idx
            elif room_free_time[room_idx] == earliest_free:
                # Tie-breaker: prefer lower room number
                if room_idx < best_room:
                    best_room = room_idx
        
        # Schedule meeting in best room
        actual_start = max(start, room_free_time[best_room])
        room_free_time[best_room] = actual_start + duration
        meeting_count[best_room] += 1
    
    # Find room with most meetings
    max_meetings = max(meeting_count)
    for room_idx in range(n):
        if meeting_count[room_idx] == max_meetings:
            return room_idx
    
    return 0

At any moment, we need to know which room will be free next (to assign delayed meetings) and which room has the lowest index among currently free rooms (to assign meetings that can start on time).

This creates two distinct tracking needs: finding the minimum free time across all rooms, and finding the minimum room index among available rooms.

If we scan through all rooms linearly for each meeting to find the next available one, we'd spend O(n) time per meeting, leading to O(n * m) total time where n is meetings and m is rooms.

By organizing rooms into priority structures (one tracking free times, one tracking available indices), we can find the next room in O(log m) time instead of O(m), making the overall algorithm much more efficient for large inputs.

Imagine a hotel with multiple rooms. When a guest arrives:

1. If any rooms are currently vacant, assign the lowest room number (room 101 before room 102)
2. If all rooms are occupied, find which room will be vacated soonest, and reserve it for this guest (they wait until that room is ready)

You'd want two lists: one showing vacant room numbers (sorted by number), and one showing occupied rooms sorted by checkout time. This dual-tracking approach maps perfectly to using two priority queues.

Use two priority queues (heaps) to efficiently track room availability. The first min-heap tracks available room indices (prioritizing lower-numbered rooms). The second min-heap tracks busy rooms by their next free time (and room index for tie-breaking). For each meeting, check if any rooms have freed up by comparing their free time to the meeting's start time. Move freed rooms from the busy heap to the available heap. Then assign the meeting to the lowest-indexed available room (or the earliest-freeing busy room if none are available). This eliminates the need to scan all rooms linearly.

import heapq
def most_booked_room(n, meetings):
    """
    Assign meetings to rooms using priority queues.
    Returns the room index that hosted the most meetings.
    """
    # Sort meetings by start time
    meetings.sort(key=lambda x: x[0])
    
    # Initialize room counters and heaps
    room_count = [0] * n
    available_rooms = list(range(n))  # Min-heap of available room indices
    heapq.heapify(available_rooms)
    busy_rooms = []  # Min-heap of (end_time, room_index)
    
    # Process each meeting
    for start, end in meetings:
        duration = end - start
        
        # Free up rooms that are available by this meeting's start time
        while busy_rooms and busy_rooms[0][0] <= start:
            end_time, room_idx = heapq.heappop(busy_rooms)
            heapq.heappush(available_rooms, room_idx)
        
        # Assign meeting to a room
        if available_rooms:
            # Use lowest-numbered available room
            room_idx = heapq.heappop(available_rooms)
            meeting_end = end
        else:
            # All rooms busy - use earliest-freeing room
            earliest_end, room_idx = heapq.heappop(busy_rooms)
            meeting_end = earliest_end + duration
        
        # Update room usage count and mark as busy
        room_count[room_idx] += 1
        heapq.heappush(busy_rooms, (meeting_end, room_idx))
    
    # Find room with maximum bookings
    max_bookings = max(room_count)
    for i in range(n):
        if room_count[i] == max_bookings:
            return i
    
    return 0

• Dual heap pattern for resource allocation: Use two min-heaps simultaneously - one tracking available resources (free room indices) and another tracking busy resources with release times (room index, end time). This pattern is essential when you need to allocate limited resources over time and always want the optimal choice (lowest room number when free, earliest available when all busy).
• Event simulation with priority queues: Sort meetings by start time first, then simulate chronologically by advancing time to the next meeting and releasing all rooms that freed up before that meeting starts. The key insight is to process room releases in bulk before each allocation, avoiding unnecessary time-step iterations.
• Tie-breaking in heap comparisons: When rooms become free at the same time, you must break ties by room index in your busy-rooms heap to ensure the lowest-numbered room is selected. Similarly, when meetings are delayed, maintain their original start time order for fair scheduling - this requires careful tuple ordering in your heap.
• Meeting delay calculation pitfall: When all rooms are busy, the delayed meeting starts at `earliest_free_time`, not at its original start time. The critical mistake is forgetting to update the meeting's end time to `earliest_free_time + duration` rather than `original_start + duration`. Always recalculate based on actual start time.
• Counting array optimization: Instead of storing which meetings went to which room, maintain a simple count array indexed by room number. After simulation, find the room with maximum count (ties broken by lowest index). This O(n) space approach is cleaner than tracking full assignment history.
• Greedy scheduling pattern: This problem exemplifies greedy resource allocation with constraints - always choose the best available option (lowest room) at each decision point. This pattern extends to CPU scheduling, parking lot systems, and any scenario where you assign tasks to limited resources with availability windows.