Meeting Rooms III

Hard
980.

Meeting Rooms III

Meeting Rooms III is a hard coding problem on arrays, sorting and simulation, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} meetings
 * @return {number}
 */
var mostBooked = function(n, meetings) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Meeting Rooms III — Solution in Python, Java & C++

Meeting Rooms III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.

Meeting Rooms III is a hard coding problem on arrays, sorting and simulation, asked in Amazon, Google and Microsoft interviews.

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.

Hints for Meeting Rooms III

  1. Hint 1

    Process the meetings in order of start time.

  2. Hint 2

    A delayed meeting keeps its length, so it ends at whenTheRoomFrees + (end - start).

  3. Hint 3

    Two pools again: free rooms by number, busy rooms by the time they free.

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

  1. Sort the meetings by start time.
  2. Free every room whose end time is at most the meeting's start.
  3. If a room is free, take the lowest-numbered one and set its end to the meeting's end.
  4. Otherwise find the earliest-freeing room — lowest number on ties — and set its end to itsEnd + (end - start).
  5. 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

Java

public static int mostBooked(int n, int[][] meetings) {
    int[][] sorted = meetings.clone();
    Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
    long[] freeAt = new long[n];
    int[] count = new int[n];
    for (int[] mt : sorted) {
        long s = mt[0], e = mt[1];
        int pick = -1;
        for (int i = 0; i < n; i++) {
            if (freeAt[i] <= s) { pick = i; break; }
        }
        if (pick >= 0) {
            freeAt[pick] = e;
            count[pick]++;
        } else {
            int best = 0;
            for (int i = 1; i < n; i++) if (freeAt[i] < freeAt[best]) best = i;
            freeAt[best] = freeAt[best] + (e - s);
            count[best]++;
        }
    }
    int ans = 0;
    for (int i = 1; i < n; i++) if (count[i] > count[ans]) ans = i;
    return ans;
}

C++

int mostBooked(int n, vector<vector<int>>& meetings) {
    vector<vector<int>> sorted = meetings;
    sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    vector<long long> freeAt(n, 0);
    vector<int> count(n, 0);
    for (auto& mt : sorted) {
        long long s = mt[0], e = mt[1];
        int pick = -1;
        for (int i = 0; i < n; i++) {
            if (freeAt[i] <= s) { pick = i; break; }
        }
        if (pick >= 0) {
            freeAt[pick] = e;
            count[pick]++;
        } else {
            int best = 0;
            for (int i = 1; i < n; i++) if (freeAt[i] < freeAt[best]) best = i;
            freeAt[best] = freeAt[best] + (e - s);
            count[best]++;
        }
    }
    int ans = 0;
    for (int i = 1; i < n; i++) if (count[i] > count[ans]) ans = i;
    return ans;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms