◀ THE GRIND — INTERVALS

Meeting Rooms III

HARD✓ CHIP-TIMEDLC #2402 — FULL STATEMENT ↗

The drill: n meeting rooms, numbered from zero. Each meeting claims the lowest-numbered free room, or waits for the soonest room to free and keeps its original length. Report the room with the most bookings — lowest index breaks a tie.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A fixed count of meeting rooms, numbered starting at zero, has to host a list of meetings, each with its own start and end time. Meetings are handled strictly in the order their start times fall, and every meeting always happens eventually — it's only a question of which room, and sometimes when.

If a room stands empty when a meeting is ready to begin, the meeting takes the lowest-numbered such room and runs for its intended length. If every room is busy instead, the meeting waits for whichever room frees up soonest, then runs there for its original duration starting from that later moment — its length never shrinks or grows because of the delay.

Once every meeting has been placed, the drill asks for the room that ended up hosting the most meetings overall. Ties go to whichever qualifying room has the smaller number.

EX 01
n = 2 · meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
→ 0
DELAYS PILE UP BUT END IN A TIE, LOWEST ROOM WINS
EX 02
n = 1 · meetings = [[0, 5], [5, 10], [10, 15]]
→ 0
SINGLE ROOM, BACK-TO-BACK MEETINGS
EX 03
n = 3 · meetings = [[1, 2], [3, 4], [5, 6]]
→ 0
NO CONTENTION, ROOM 0 IS ALWAYS FREE FIRST
THE HINTS — TAKE ONLY WHAT YOU NEED
HINT 1 THE NUDGE

Meetings must be handled start-time first. At every step you need two things ready fast: which rooms are free right now, and — if none are — which room frees up soonest.

HINT 2 THE STRUCTURE

Two min-heaps do the job: one holding free room numbers (lowest always on top), one holding (end time, room) pairs for busy rooms (soonest end always on top). Before assigning a meeting, drain every busy room whose end time has already passed into the free heap.

HINT 3 ONE STEP FROM THE ANSWER

If the free heap has a room, take it and push (this meeting's end, room) onto the busy heap. Otherwise pop the soonest-ending busy room, and re-push it with end = that free time plus this meeting's original duration, on the SAME room. Tally bookings per room and report the max, ties to the lowest index.

COACH'S BOARD — THE PATTERN, STEP BY STEP
TWO HEAPS: FREE + BUSYPATTERN · HEAP SIMULATIONn = 2 rooms · meetings = [0,10],[1,5],[2,7],[3,4]
[0,10]
[1,5]
[2,7]
[3,4]
ROOM 0 / ROOM 1 — end, count
room 0 → free, count 0
room 1 → free, count 0
STEP 1

2 rooms, meetings sorted by start: [0,10],[1,5],[2,7],[3,4]. Lowest free room goes first; a full house waits for the soonest release.

STEP 1 / 7 · ← → WORK TOO
THE SPLITS — TWO PACES, TWO LANGUAGES
grind/meeting-rooms-iii.py — RACE PACE
LANG ▸
PACE ▸
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        ordered = sorted(meetings)
        free = list(range(n))  # min-heap of free room numbers
        busy = []  # min-heap of (end_time, room)
        counts = [0] * n
        i = 0

        for start, end in ordered:
            while busy and busy[0][0] <= start:
                _, r = heapq.heappop(busy)
                heapq.heappush(free, r)

            if free:
                r = heapq.heappop(free)
                heapq.heappush(busy, (end, r))
                counts[r] += 1
            else:
                free_time, r = heapq.heappop(busy)
                heapq.heappush(busy, (free_time + (end - start), r))
                counts[r] += 1

        best = 0
        for r in range(1, n):
            if counts[r] > counts[best]:
                best = r
        return best
TIME O(M LOG N)SPACE O(N)PYTHON · RACE PACE · 27 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED