Meeting Rooms III — Most Booked Room

Problem Statement

There are n rooms numbered 0 … n − 1. Each meeting picks the lowest-numbered free room; if every room is busy, the meeting waits until the earliest-finishing room frees up — keeping its original duration. Return the room that held the most meetings (ties → the lowest number).

Input

• n — total number of rooms.
• meetings — list of [start, end] intervals.

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

Output

A single integer — the index of the most-booked room.

0

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ meetings.length ≤ 10⁵
• meetings[i].length == 2
• 0 ≤ startᵢ < endᵢ ≤ 5·10⁵

Intuition

Sort the meetings by start time and simulate with two heaps:

• avail — a min-heap of free room numbers.
• busy — a min-heap of (end_time, room) for currently-occupied rooms.

For each meeting:

1. Pop every room from busy whose end_time ≤ meeting.start — they’re free now, push to avail.
2. If avail is non-empty → pick the smallest room and push it onto busy with end.
3. Otherwise → pop the earliest-finishing room from busy, delay the meeting so it starts exactly when that room frees, push back (free_time + duration, room).
4. Increment a count[room] tally.

Finally return the index with the highest count (lowest index breaks ties).

Solution

import heapq
 
def mostBooked(n: int, meetings: list[list[int]]) -> int:
    meetings.sort()
    count = [0] * n
    avail = list(range(n))      # min-heap of available room numbers
    busy = []                   # min-heap of (end_time, room)
 
    for start, end in meetings:
        # Free up rooms that have finished
        while busy and busy[0][0] <= start:
            _, room = heapq.heappop(busy)
            heapq.heappush(avail, room)
 
        if avail:
            room = heapq.heappop(avail)
            heapq.heappush(busy, (end, room))
        else:
            free_time, room = heapq.heappop(busy)
            heapq.heappush(busy, (free_time + end - start, room))
 
        count[room] += 1
 
    return count.index(max(count))

// Simplified — in production, use a proper MinHeap class.
function mostBooked(n: number, meetings: number[][]): number {
    meetings.sort((a, b) => a[0] - b[0]);
    const count = new Array(n).fill(0);
    const endTimes = new Array(n).fill(0); // when each room frees up
 
    for (const [start, end] of meetings) {
        let bestRoom = -1, earliest = Infinity;
        for (let r = 0; r < n; r++) {
            if (endTimes[r] <= start) { bestRoom = r; break; }
            if (endTimes[r] < earliest) { earliest = endTimes[r]; bestRoom = r; }
        }
        const wait = Math.max(0, endTimes[bestRoom] - start);
        endTimes[bestRoom] = start + wait + (end - start);
        count[bestRoom]++;
    }
 
    return count.indexOf(Math.max(...count));
}

Complexity

Edge Case Thinking