LeetCode 2402 - Meeting Rooms III

LeetCode Problem 2402

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Sorting, Heap (Priority Queue), Simulation

Solution

Problem Understanding

The problem is about scheduling meetings into a fixed number of rooms, where each meeting has a unique start time and a defined duration. We have n rooms numbered from 0 to n - 1, and we are given a list of meetings represented as [start, end) intervals. The task is to assign each meeting to a room according to specific rules: always use the lowest-numbered available room, delay meetings if no room is free, and when multiple meetings are waiting, prioritize the one with the earliest original start time. After all meetings are assigned, we need to determine which room hosted the most meetings, breaking ties by choosing the room with the lowest number.

The input guarantees unique start times, so no two meetings start simultaneously. Constraints are moderate: up to 100 rooms and up to 100,000 meetings. This rules out naive approaches that scan all rooms for each meeting, because an O(n * m) solution could reach 10 million operations, which is borderline acceptable but inefficient. Important edge cases include situations where all rooms are busy and meetings are delayed, the smallest input (n = 1, meetings has one element), or when all rooms end up hosting the same number of meetings.

Approaches

The brute-force approach would be to simulate the timeline by iterating over each meeting in chronological order, checking all rooms for availability, and assigning meetings to the first free room. If no room is free, you would increment the time step by step until a room becomes available. While correct, this approach is inefficient because the timeline can extend up to 5 * 10^5 and we may need to check every room at each time step, giving a worst-case complexity of O(n * maxTime) which is too slow.

The optimal approach uses two priority queues (min-heaps). One heap tracks available rooms by their number, allowing us to always get the lowest-numbered free room in O(log n) time. The other heap tracks occupied rooms by their finish time, so we can efficiently know which room becomes free next. We sort meetings by their start time and process them sequentially. When a meeting cannot start because all rooms are occupied, we delay it to the earliest room release time, preserving its original duration. This ensures we efficiently manage room allocation and meeting delays.

Algorithm Walkthrough

1. Sort Meetings: Sort the meetings by their original start times so we always process the earliest meeting first.
2. Initialize Heaps: Create a min-heap for available rooms ordered by room number, initially containing all rooms from 0 to n-1. Create a min-heap for occupied rooms ordered by end time, storing tuples (endTime, roomNumber).
3. Process Each Meeting: Iterate over each meeting in sorted order.
4. Free Rooms: Before assigning a room, check the occupied heap and release any rooms whose meetings have ended before or at the current meeting start time. Push these rooms back to the available heap.
5. Assign Room: If an available room exists, pop the smallest-numbered room and schedule the meeting. If no room is free, pop the room that finishes earliest from the occupied heap, and delay the meeting to start at that end time while preserving its duration.
6. Update Counts: Maintain a counter array roomCounts that tracks the number of meetings each room hosts.
7. Determine Result: After all meetings are scheduled, return the room number with the maximum count. In case of a tie, the min-room number naturally resolves it because the array index corresponds to room number.

Why it works: The algorithm maintains the invariant that available rooms are always in order and that delayed meetings respect their original start time and duration. Using heaps ensures that both room selection and release are efficient and correct according to the problem rules.

Python Solution

from typing import List
import heapq

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        # Sort meetings by start time
        meetings.sort()
        
        # Initialize available rooms heap
        available = list(range(n))
        heapq.heapify(available)
        
        # Heap to track ongoing meetings: (end_time, room_number)
        occupied = []
        
        # Count of meetings per room
        room_counts = [0] * n
        
        for start, end in meetings:
            # Free up rooms that have finished before the current meeting starts
            while occupied and occupied[0][0] <= start:
                finish_time, room = heapq.heappop(occupied)
                heapq.heappush(available, room)
            
            if available:
                room = heapq.heappop(available)
                actual_start = start
            else:
                finish_time, room = heapq.heappop(occupied)
                actual_start = finish_time  # delay meeting
            actual_end = actual_start + (end - start)
            heapq.heappush(occupied, (actual_end, room))
            room_counts[room] += 1
        
        # Return the room with the most meetings (ties broken by smallest index)
        return room_counts.index(max(room_counts))

Explanation: We first sort meetings to process them in chronological order. Two heaps manage room availability and meeting finish times efficiently. For each meeting, we free rooms that have become available, then either assign the earliest free room or delay the meeting if all rooms are occupied. The counts array tracks meeting assignments to determine the most-used room.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

type Room struct {
    endTime int
    index   int
}

type MinHeap []Room

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].endTime < h[j].endTime || (h[i].endTime == h[j].endTime && h[i].index < h[j].index) }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x any)        { *h = append(*h, x.(Room)) }
func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func mostBooked(n int, meetings [][]int) int {
    sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })

    available := &IntHeap{}
    heap.Init(available)
    for i := 0; i < n; i++ {
        heap.Push(available, i)
    }

    occupied := &MinHeap{}
    heap.Init(occupied)

    counts := make([]int, n)

    for _, m := range meetings {
        start, end := m[0], m[1]

        // Free rooms
        for occupied.Len() > 0 && (*occupied)[0].endTime <= start {
            room := heap.Pop(occupied).(Room)
            heap.Push(available, room.index)
        }

        var room int
        actualStart := start
        if available.Len() > 0 {
            room = heap.Pop(available).(int)
        } else {
            r := heap.Pop(occupied).(Room)
            room = r.index
            actualStart = r.endTime
        }
        actualEnd := actualStart + (end - start)
        heap.Push(occupied, Room{actualEnd, room})
        counts[room]++
    }

    maxCount, ans := 0, 0
    for i, c := range counts {
        if c > maxCount {
            maxCount = c
            ans = i
        }
    }
    return ans
}

// Helper IntHeap for available rooms
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

Go-specific notes: Go requires explicit heap implementation for both available rooms and occupied rooms. The MinHeap for occupied rooms tracks both end time and room index to resolve ties. IntHeap is used for available rooms for simple integer comparison.

Worked Examples

Example 1: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]