Meeting Rooms III

You are given an integer n. There are n rooms numbered from 0 to n - 1. You are given a 2D integer array meetings where meetings[i] = [start_i, end_i] means that a meeting will be held during the half-closed time interval [start_i, end_i). All the values of start_i are unique.

Most Booked Meeting Room

Problem Statement

You are given a number n. There are n rooms, numbered from 0 to n - 1.

You are also given a 2D array called meetings. Each entry, meetings[i] = [start_i, end_i], tells us that a meeting happens during the time period [start_i, end_i). This means the meeting includes the start time but does not include the end time. All the start times are different from each other.

Meetings are given to rooms using these rules:

1. Each meeting goes into the free room with the lowest number.
2. If no room is free, the meeting is delayed until a room opens up. The delayed meeting keeps the same duration as before.
3. When a room becomes free, meetings with an earlier original start time get priority for that room.

Return the number of the room that held the most meetings. If more than one room is tied for the most, return the room with the lowest number.

A half-closed interval [a, b) means the range from a to b, including a but not including b.

Examples

Example 1

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

Output: 0

Explanation:

• At time 0, both rooms are free. The first meeting starts in room 0.
• At time 1, only room 1 is free. The second meeting starts in room 1.
• At time 2, both rooms are busy. The third meeting is delayed.
• At time 3, both rooms are busy. The fourth meeting is delayed.
• At time 5, the meeting in room 1 finishes. The third meeting starts in room 1, running from [5,10).
• At time 10, both meetings finish. The fourth meeting starts in room 0, running from [10,11).

Rooms 0 and 1 both held 2 meetings. Since they are tied, we return the lower number, 0.

Example 2

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

Output: 1

Explanation:

• At time 1, all three rooms are free. The first meeting starts in room 0.
• At time 2, rooms 1 and 2 are free. The second meeting starts in room 1.
• At time 3, only room 2 is free. The third meeting starts in room 2.
• At time 4, all rooms are busy. The fourth meeting is delayed.
• At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2, running from [5,10).
• At time 6, all rooms are busy. The fifth meeting is delayed.
• At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1, running from [10,12).

Room 0 held 1 meeting. Rooms 1 and 2 each held 2 meetings. So we return 1.

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ meetings.length ≤ 10⁵
• meetings[i].length == 2
• 0 ≤ start_i < end_i ≤ 5 × 10⁵
• All start times are different from each other.

Naive Solution

The steps for this simple approach:

• We create an array called rooms. This stores the end time of the current meeting in each room.
• We create another array called meetingCount. This tracks how many meetings each room has held.
• We sort all the meetings by their start time.
• For each meeting, we check every room. If a room's current end time is less than or equal to the meeting's start time, that room is free. We assign the meeting there, update its end time, and increase its meeting count.
• If no room is free, we find the room that will free up soonest (the one with the lowest end time). We delay the meeting there. Its new end time becomes: previous end time + (meeting duration).
• At the end, we look through meetingCount and find the room with the highest count. If there's a tie, the lowest room number wins automatically, since we scan from left to right.

Naive Code

var mostBooked = function (n, meetings) {
    //create array for rooms which will store end time of meetings
    // create a array for count of each meeting
    // sort meetings array with arrival time
    // for each meetings check available room end time >= meetings start time
    // if yes update end time, count of room and break
    // if no rooms are found update end time of meeting with lowest end time with end-start
    // find max count of room array

    var rooms = new Array(n).fill(0);
    var meetingCount = new Array(n).fill(0);
    var sortedMeetings = meetings.sort((a, b) => a[0] - b[0]);

    for (const meet of sortedMeetings) {
        let lowestIdx = 0;
        var roomUpdated = false
        for (let i = 0; i < rooms.length; i++) {
            if (rooms[i] < rooms[lowestIdx]) {
                lowestIdx = i;
            }

            if (meet[0] >= rooms[i]) {
                rooms[i] = meet[1]; // update the room's end time
                meetingCount[i] = meetingCount[i] + 1;
                roomUpdated = true;
                break;
            }
        }

        if (!roomUpdated) {
            rooms[lowestIdx] = rooms[lowestIdx] + meet[1] - meet[0];
            meetingCount[lowestIdx] = meetingCount[lowestIdx] + 1;
        }
    }

    let maxMeetingCount = -Infinity;
    let maxIndex = 0;
    for (let i = 0; i < meetingCount.length; i++) {
        if (meetingCount[i] > maxMeetingCount) {
            maxMeetingCount = meetingCount[i];
            maxIndex = i;
        }
    }

    return maxIndex;
};

This works, but it checks every room for every meeting. This can get slow when there are many rooms and many meetings.

Optimized Solution

To make this faster, we use two heaps instead of scanning every room each time:

• A min heap called availableRooms. This stores the numbers of free rooms, so we can always grab the lowest-numbered free room quickly.
• A min heap called busyRooms. This stores [endTime, roomNumber] pairs, so we can always find the room that will free up soonest.

Here is how it works:

• We start by putting all room numbers into availableRooms, since every room is free at the beginning.
• We sort the meetings by start time.
• For each meeting:
  • First, we check busyRooms. Any room whose meeting has already ended by this meeting's start time gets moved back into availableRooms.
  • If availableRooms is not empty, we take the lowest-numbered free room. We assign the meeting there, increase its meeting count, and push its new end time into busyRooms.
  • If availableRooms is empty, no room is free. We take the room from busyRooms that frees up soonest. We delay the meeting there. Its new end time becomes: (the room's free time) + (meeting duration).
• At the end, we scan meetingCount to find the room with the highest count, just like before.

This avoids checking every single room for every meeting, which makes it much faster for large inputs.

Optimized Code

class MinHeap {
  constructor(comparator) {
    this.heap = [];
    this.comparator = comparator;
  }

  size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
  peek() { return this.heap[0]; }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._bubbleDown(0);
    }
    return top;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.comparator(this.heap[parent], this.heap[i]) <= 0) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _bubbleDown(i) {
    const n = this.heap.length;
    while (true) {
      const left = 2 * i + 1, right = 2 * i + 2;
      let smallest = i;
      if (left < n && this.comparator(this.heap[left], this.heap[smallest]) < 0) smallest = left;
      if (right < n && this.comparator(this.heap[right], this.heap[smallest]) < 0) smallest = right;
      if (smallest === i) break;
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

var mostBooked = function (n, meetings) {
  const meetingCount = new Array(n).fill(0);

  const sortedMeetings = [...meetings].sort((a, b) => a[0] - b[0]);

  const availableRooms = new MinHeap((a, b) => a - b);            // just room numbers
  const busyRooms = new MinHeap((a, b) => a[0] - b[0]);           // [endTime, roomNumber]

  for (let i = 0; i < n; i++) {
    availableRooms.push(i);
  }

  for (const [start, end] of sortedMeetings) {
    // Free every room whose meeting has ended by this meeting's start time
    while (!busyRooms.isEmpty() && busyRooms.peek()[0] <= start) {
      const [, roomNumber] = busyRooms.pop();
      availableRooms.push(roomNumber);
    }

    if (!availableRooms.isEmpty()) {
      // A room is free right now — take the lowest-numbered one
      const room = availableRooms.pop();
      meetingCount[room]++;
      busyRooms.push([end, room]);
    } else {
      // No room free — delay until the soonest-freeing room opens up
      const [freeTime, room] = busyRooms.pop();
      const duration = end - start;
      meetingCount[room]++;
      busyRooms.push([freeTime + duration, room]);
    }
  }

  let maxCount = -Infinity;
  let maxIndex = 0;
  for (let i = 0; i < meetingCount.length; i++) {
    if (meetingCount[i] > maxCount) {
      maxCount = meetingCount[i];
      maxIndex = i;
    }
  }

  return maxIndex;
};