378. Meeting Rooms III

Process meetings by start time. Keep a min-heap of free room numbers and a min-heap of busy rooms keyed by (end time, room). Free up rooms whose end <= now; assign the lowest free room, or if none, delay onto the room that frees earliest (breaking ties by lowest number).

Simulate with two priority queues

Sort meetings by start. Maintain:

• free — a min-heap of available room numbers (lowest first).
• busy — a min-heap of (end_time, room) for occupied rooms (earliest-freeing first, ties by room number).

A per-room counter cnt[room] tallies how many meetings each room held.

For each meeting [s, e):

1. Release every busy room with end_time <= s back into free.
2. If free is non-empty, take the lowest free room r, push (e, r) onto busy.
3. Otherwise delay: pop the earliest-freeing (et, r) from busy, and re-push (et + (e - s), r) — the meeting starts when the room frees and keeps its duration.
4. cnt[r] += 1.

Answer: the room with the max count (lowest number on ties).

Worked example

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

• [0,10] → room 0. [1,5] → room 1. [2,7] → both busy; delay onto room 1 (frees at 5) → runs [5,10). [3,4] → delay onto room 0 (frees at 10) → runs [10,11).
• Counts: room 0 held 2 meetings, room 1 held 2. Tie → lowest room → 0.

Complexity

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

import java.util.*;

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> free = new PriorityQueue<>();
        for (int i = 0; i < n; i++) free.offer(i);
        // busy: (endTime, room), earliest-freeing first, ties by lower room
        PriorityQueue<long[]> busy = new PriorityQueue<>((x, y) ->
            x[0] != y[0] ? Long.compare(x[0], y[0]) : Long.compare(x[1], y[1]));
        int[] cnt = new int[n];
        for (int[] m : meetings) {
            long s = m[0], e = m[1];
            while (!busy.isEmpty() && busy.peek()[0] <= s) {
                free.offer((int) busy.poll()[1]);
            }
            int r;
            if (!free.isEmpty()) {
                r = free.poll();
                busy.offer(new long[]{e, r});
            } else {
                long[] top = busy.poll();
                r = (int) top[1];
                busy.offer(new long[]{top[0] + (e - s), r});
            }
            cnt[r]++;
        }
        int best = 0;
        for (int i = 1; i < n; i++) {
            if (cnt[i] > cnt[best]) best = i;
        }
        return best;
    }
}