Meeting Rooms III

hard array sorting heap

Problem

You are given n meeting rooms numbered 0..n-1 and a list of meetings [start, end). Process meetings in order of start time: assign to the lowest-numbered free room; if no room is free, wait for the earliest one to free up and run a meeting of the same duration there. Return the room that hosts the most meetings.

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

Output0

Rooms 0 and 1 each host two meetings; tie broken by lower index.

meetings (s:e separated by ';')

import heapq

def most_booked(n, meetings):
    meetings.sort()
    free = list(range(n))
    heapq.heapify(free)
    busy = []  # (end_time, room)
    counts = [0] * n
    for s, e in meetings:
        while busy and busy[0][0] <= s:
            _, r = heapq.heappop(busy)
            heapq.heappush(free, r)
        if free:
            r = heapq.heappop(free)
            heapq.heappush(busy, (e, r))
        else:
            end, r = heapq.heappop(busy)
            heapq.heappush(busy, (end + (e - s), r))
        counts[r] += 1
    best = 0
    for i in range(1, n):
        if counts[i] > counts[best]:
            best = i
    return best

function mostBooked(n, meetings) {
  meetings.sort((a, b) => a[0] - b[0]);
  const free = Array.from({length: n}, (_, i) => i); // min-heap of indices
  const busy = []; // min-heap of [endTime, room]
  const counts = new Array(n).fill(0);
  const cmpFree = (a, b) => a - b;
  const cmpBusy = (a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1];
  // (use a proper heap in production; pseudocode here)
  for (const [s, e] of meetings) {
    while (busy.length && busy[0][0] <= s) free.push(busy.shift()[1]);
    free.sort(cmpFree); busy.sort(cmpBusy);
    let r;
    if (free.length) {
      r = free.shift();
      busy.push([e, r]); busy.sort(cmpBusy);
    } else {
      const top = busy.shift();
      r = top[1];
      busy.push([top[0] + (e - s), r]); busy.sort(cmpBusy);
    }
    counts[r]++;
  }
  let best = 0;
  for (let i = 1; i < n; i++) if (counts[i] > counts[best]) best = i;
  return best;
}

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> free = new PriorityQueue<>();
        for (int i = 0; i < n; i++) free.offer(i);
        PriorityQueue<long[]> busy = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
        int[] counts = 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}); }
            counts[r]++;
        }
        int best = 0;
        for (int i = 1; i < n; i++) if (counts[i] > counts[best]) best = i;
        return best;
    }
}

int mostBooked(int n, vector<vector<int>>& meetings) {
    sort(meetings.begin(), meetings.end());
    priority_queue<int, vector<int>, greater<>> free;
    for (int i = 0; i < n; i++) free.push(i);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> busy;
    vector<int> counts(n, 0);
    for (auto& m : meetings) {
        long long s = m[0], e = m[1];
        while (!busy.empty() && busy.top().first <= s) { free.push(busy.top().second); busy.pop(); }
        int r;
        if (!free.empty()) { r = free.top(); free.pop(); busy.push({e, r}); }
        else { auto top = busy.top(); busy.pop(); r = top.second; busy.push({top.first + (e - s), r}); }
        counts[r]++;
    }
    int best = 0;
    for (int i = 1; i < n; i++) if (counts[i] > counts[best]) best = i;
    return best;
}

Explanation

We process meetings in start-time order and assign each one a room, then report the room that hosted the most meetings. The clean way to manage rooms is with two heaps.

The free heap is a min-heap of room indices that are currently idle (so we always grab the lowest-numbered free room). The busy heap holds (end_time, room) pairs, ordered by end time, telling us when each occupied room frees up.

For each meeting, we first release rooms: while the soonest-ending busy room finishes at or before this meeting's start, we pop it from busy and push it back to free. Then, if a room is free, we use the smallest-index one and record its end time.

If no room is free, the meeting must wait: we take the room that frees up earliest and run there, but the meeting keeps its full duration, so its new end is oldEnd + (e - s). Either way we bump counts[room].

Example: n=2, meetings=[[0,10],[1,5],[2,7],[3,4]]. Rooms 0 and 1 each end up hosting two meetings; ties go to the lower index, so the answer is room 0.

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