2402. Meeting Rooms III

NeetCode: Meeting Rooms III · LeetCode: 2402. Meeting Rooms III · Difficulty: Hard

There are n rooms numbered 0..n-1 and an array of meetings [start, end) with all start times unique. Meetings are handled in order of start time. Each meeting takes the lowest-numbered free room. If no room is free, it waits until the earliest room frees up (lowest number on ties), and it keeps its original duration, so it ends at newStart + (end - start). Return the room that held the most meetings; if several tie, return the lowest number.

Example

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

For the first example: room 0 takes [0,10), room 1 takes [1,5). Meeting [2,7) waits until 5 and runs [5,10) in room 1. Meeting [3,4) waits until 10 and runs [10,11) in room 0. Rooms 0 and 1 have two meetings each, so the answer is 0.

Brute force: scan all rooms for every meeting

Sort meetings by start. Track freeAt[r], the time room r becomes free, and count[r]. For each meeting, scan the rooms in order: the first with freeAt[r] <= start is used immediately. If none is free, choose the room with the smallest freeAt (first one on ties) and delay the meeting to that time. That is one O(n) scan per meeting. Delays accumulate, so end times can exceed the int range (up to about 5 * 10^5 per meeting times up to 10^5 meetings); freeAt is a long[].

import java.util.Arrays;

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        int[][] ms = meetings.clone();
        Arrays.sort(ms, (a, b) -> Integer.compare(a[0], b[0]));
        long[] freeAt = new long[n];
        int[] count = new int[n];
        for (int[] m : ms) {
            long start = m[0];
            long len = m[1] - m[0];
            int room = -1;
            for (int r = 0; r < n; r++) {
                if (freeAt[r] <= start) {
                    room = r;
                    break;
                }
            }
            if (room != -1) {
                freeAt[room] = start + len;
            } else {
                room = 0;
                for (int r = 1; r < n; r++) {
                    if (freeAt[r] < freeAt[room]) {
                        room = r;
                    }
                }
                freeAt[room] += len;
            }
            count[room]++;
        }
        int best = 0;
        for (int r = 1; r < n; r++) {
            if (count[r] > count[best]) {
                best = r;
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.mostBooked(2, new int[][] {{0, 10}, {1, 5}, {2, 7}, {3, 4}}));
        System.out.println(solution.mostBooked(3, new int[][] {{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}}));
        System.out.println(solution.mostBooked(1, new int[][] {{5, 6}}));
    }
}

0
1
0

Time: O(m log m + m · n) for m meetings and n rooms. Space: O(m + n).

Optimal: two heaps

Two min-heaps replace the room scan:

• free: numbers of free rooms, so the top is the lowest-numbered free room.
• busy: {endTime, room} for occupied rooms, so the top is the room that frees first. The comparator breaks ties on end time by the lower room number.

PriorityQueue is a min-heap, which is the order both heaps need. The comparators use Long.compare and Integer.compare, never subtraction.

The delay rule: if no room is free at start, the meeting waits for the earliest-ending room, begins at that end, and keeps its duration, so it finishes at end + (oldEnd - oldStart).

For each meeting in start order:

1. Move every busy room with end <= start back into free.
2. If free has a room, use the lowest one and begin at start. Otherwise poll the earliest {end, room} from busy and begin at end (the delay).
3. Add {begin + duration, room} to busy and increment count[room].

Trace for the first example (n = 2): [0,10) goes to room 0, [1,5) to room 1; [2,7) finds no free room, so it takes room 1 (ends at 5) and runs [5,10); [3,4) waits for room 0 (ends at 10) and runs [10,11). Counts are [2, 2], so the answer is 0.

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        int[][] ms = meetings.clone();
        Arrays.sort(ms, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> free = new PriorityQueue<>();
        for (int r = 0; r < n; r++) {
            free.add(r);
        }
        // Each entry is {end time, room}.
        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) ->
                a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
        int[] count = new int[n];
        for (int[] m : ms) {
            long start = m[0];
            long len = m[1] - m[0];
            while (!busy.isEmpty() && busy.peek()[0] <= start) {
                free.add((int) busy.poll()[1]);
            }
            int room;
            long begin;
            if (!free.isEmpty()) {
                room = free.poll();
                begin = start;
            } else {
                long[] earliest = busy.poll(); // delayed until this room frees up
                room = (int) earliest[1];
                begin = earliest[0];
            }
            busy.add(new long[] {begin + len, room});
            count[room]++;
        }
        int best = 0;
        for (int r = 1; r < n; r++) {
            if (count[r] > count[best]) {
                best = r;
            }
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.mostBooked(2, new int[][] {{0, 10}, {1, 5}, {2, 7}, {3, 4}}));
        System.out.println(solution.mostBooked(3, new int[][] {{1, 20}, {2, 10}, {3, 5}, {4, 9}, {6, 8}}));
        System.out.println(solution.mostBooked(1, new int[][] {{5, 6}}));
    }
}

0
1
0

Time: O(m log m + m log n). Space: O(m + n).

busy.poll() never returns null in the else branch: if free is empty then all n >= 1 rooms are busy. The last loop scans rooms from low to high and replaces the best only on a strictly larger count, so the lowest room number wins ties.

How to explain it in an interview

• Start with: sort by start, keep each room's free time, and scan all rooms for every meeting; O(m * n).
• Key insight: only the lowest free room number and the earliest-finishing busy room are needed, which are two heap tops.
• Code it in steps: (1) sort meetings; (2) free heap of all rooms, busy heap of {end, room}, count; (3) release rooms whose end <= start; (4) pick a free room, or take the earliest busy one and start at its end; (5) add the new end, bump the count; (6) return the lowest room with the max count.
• Complexity: O(m log m) to sort plus O(log n) heap work per meeting; O(n + m) space.
• Pitfalls: use long for times since delays accumulate; release rooms with end <= start (not <); a delayed meeting keeps its duration; ties on end time go to the lower room, which the comparator provides.