Question

2402. Meeting Rooms III

中文文档

Description

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] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.
2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
3. When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return_ the number of the room that held the most meetings. _If there are multiple rooms, return_ the room with the lowest number._

A half-closed interval [a, b) is the interval between a and b including a and not including b.

 

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 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 not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1. 

 

Constraints:

• 1 <= n <= 100
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 105
• All the values of starti are unique.

Solutions

Solution 1: Priority Queue (Min Heap)

We define two priority queues, representing idle meeting rooms and busy meeting rooms, respectively. Among them: the idle meeting rooms idle are sorted according to index; while the busy meeting rooms busy are sorted according to end time, index.

First, sort the meetings by start time, then traverse the meetings. For each meeting:

• If there is a busy meeting room that is less than or equal to the start time of the current meeting, add it to the idle meeting room queue idle.
• If there are currently idle meeting rooms, take out the meeting room with the smallest weight from the idle queue idle and add it to the busy queue busy.
• If there are currently no idle meeting rooms, find the meeting room with the earliest end time and smallest index in the busy queue busy, and re-add it to the busy queue busy.

The time complexity is $O(m \times \log m)$, where $m$ is the number of meetings.

Similar problems:

• 1882. Process Tasks Using Servers

class Solution:
  def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
    meetings.sort()
    busy = []
    idle = list(range(n))
    heapify(idle)
    cnt = [0] * n
    for s, e in meetings:
      while busy and busy[0][0] <= s:
        heappush(idle, heappop(busy)[1])
      if idle:
        i = heappop(idle)
        cnt[i] += 1
        heappush(busy, (e, i))
      else:
        a, i = heappop(busy)
        cnt[i] += 1
        heappush(busy, (a + e - s, i))
    ans = 0
    for i, v in enumerate(cnt):
      if cnt[ans] < v:
        ans = i
    return ans

class Solution {
  public int mostBooked(int n, int[][] meetings) {
    Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
    PriorityQueue<int[]> busy
      = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    PriorityQueue<Integer> idle = new PriorityQueue<>();
    for (int i = 0; i < n; ++i) {
      idle.offer(i);
    }
    int[] cnt = new int[n];
    for (var v : meetings) {
      int s = v[0], e = v[1];
      while (!busy.isEmpty() && busy.peek()[0] <= s) {
        idle.offer(busy.poll()[1]);
      }
      int i = 0;
      if (!idle.isEmpty()) {
        i = idle.poll();
        busy.offer(new int[] {e, i});
      } else {
        var x = busy.poll();
        i = x[1];
        busy.offer(new int[] {x[0] + e - s, i});
      }
      ++cnt[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (cnt[ans] < cnt[i]) {
        ans = i;
      }
    }
    return ans;
  }
}

using ll = long long;
using pii = pair<ll, int>;

class Solution {
public:
  int mostBooked(int n, vector<vector<int>>& meetings) {
    priority_queue<int, vector<int>, greater<int>> idle;
    priority_queue<pii, vector<pii>, greater<pii>> busy;
    for (int i = 0; i < n; ++i) idle.push(i);
    vector<int> cnt(n);
    sort(meetings.begin(), meetings.end());
    for (auto& v : meetings) {
      int s = v[0], e = v[1];
      while (!busy.empty() && busy.top().first <= s) {
        idle.push(busy.top().second);
        busy.pop();
      }
      int i = 0;
      if (!idle.empty()) {
        i = idle.top();
        idle.pop();
        busy.push({e, i});
      } else {
        auto x = busy.top();
        busy.pop();
        i = x.second;
        busy.push({x.first + e - s, i});
      }
      ++cnt[i];
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (cnt[ans] < cnt[i]) {
        ans = i;
      }
    }
    return ans;
  }
};

func mostBooked(n int, meetings [][]int) int {
  sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
  idle := hp{make([]int, n)}
  for i := 0; i < n; i++ {
    idle.IntSlice[i] = i
  }
  busy := hp2{}
  cnt := make([]int, n)
  for _, v := range meetings {
    s, e := v[0], v[1]
    for len(busy) > 0 && busy[0].end <= s {
      heap.Push(&idle, heap.Pop(&busy).(pair).i)
    }
    var i int
    if idle.Len() > 0 {
      i = heap.Pop(&idle).(int)
      heap.Push(&busy, pair{e, i})
    } else {
      x := heap.Pop(&busy).(pair)
      i = x.i
      heap.Push(&busy, pair{x.end + e - s, i})
    }
    cnt[i]++
  }
  ans := 0
  for i, v := range cnt {
    if cnt[ans] < v {
      ans = i
    }
  }
  return ans
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}

type pair struct{ end, i int }
type hp2 []pair

func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
  a, b := h[i], h[j]
  return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any)   { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }