Meeting Rooms III — Hard Problem & Solution

There are n meeting rooms numbered 0 … n - 1. meetings[i] = [start, end] is a half-open interval, and all the start times are different.

Difficulty: Hard
Topics: Arrays, Sorting, Simulation, Heap
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

There are n meeting rooms numbered 0 … n - 1. meetings[i] = [start, end] is a half-open interval, and all the start times are different.

Meetings are handled in order of start time. A meeting takes the lowest-numbered free room. If every room is busy, it is delayed — keeping its original duration — until a room frees, and then takes the lowest-numbered room that frees earliest. Return the room that held the most meetings, breaking ties by the lowest number.

Example 1

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation: Both rooms hold two meetings, so the lower number wins.

Example 2

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1

Example 3

Input: n = 1, meetings = [[0,5],[5,10]]
Output: 0

Constraints

1 <= n <= 100
1 <= meetings.length <= 1000
meetings[i].length == 2
0 <= start < end <= 5 * 10^5
All the values of start are unique.

How to solve Meeting Rooms III

Simulate. Sort by start time, and for each meeting either take the lowest-numbered free room or delay it into the room that frees soonest, extending its end by the meeting's original duration.

Approach

Sort the meetings by start time.
Free every room whose end time is at most the meeting's start.
If a room is free, take the lowest-numbered one and set its end to the meeting's end.
Otherwise find the earliest-freeing room — lowest number on ties — and set its end to itsEnd + (end - start).
Count bookings per room and return the busiest, lowest number first.

Why it works

Keeping the original duration on a delayed meeting is the rule that makes the simulation non-trivial: a delayed meeting pushes its room's free time further out than the meeting's own end would suggest, which cascades into later decisions. Tie-breaking by room number in both branches is what makes the answer well defined.

Complexity

Time — O(m log m + m · n) as written, or O((m + n) log n) with two heaps
Space — O(n)

Pitfalls

A delayed meeting does not end at its original end.
Rooms freeing exactly at the start time are available.
Ties on the earliest free time go to the lower room number.

Reference solution

Python

from typing import List
import heapq

def mostBooked(n: int, meetings: List[List[int]]) -> int:
    ordered = sorted(meetings, key=lambda m: m[0])
    free = list(range(n))
    heapq.heapify(free)
    busy = []
    count = [0] * n
    for start, end in ordered:
        while busy and busy[0][0] <= start:
            _, room = heapq.heappop(busy)
            heapq.heappush(free, room)
        if free:
            room = heapq.heappop(free)
            heapq.heappush(busy, (end, room))
        else:
            done, room = heapq.heappop(busy)
            heapq.heappush(busy, (done + (end - start), room))
        count[room] += 1
    best = 0
    for i in range(1, n):
        if count[i] > count[best]:
            best = i
    return best

JavaScript

var mostBooked = function(n, meetings) {
    var sorted = meetings.slice();
    sorted.sort(function(a, b) { return a[0] - b[0]; });
    var freeAt = [], count = [], i;
    for (i = 0; i < n; i++) { freeAt.push(0); count.push(0); }
    for (var t = 0; t < sorted.length; t++) {
        var s = sorted[t][0], e = sorted[t][1];
        var pick = -1;
        for (i = 0; i < n; i++) {
            if (freeAt[i] <= s) { pick = i; break; }
        }
        if (pick >= 0) {
            freeAt[pick] = e;
            count[pick]++;
        } else {
            var best = 0;
            for (i = 1; i < n; i++) if (freeAt[i] < freeAt[best]) best = i;
            freeAt[best] = freeAt[best] + (e - s);
            count[best]++;
        }
    }
    var ans = 0;
    for (i = 1; i < n; i++) if (count[i] > count[ans]) ans = i;
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue