Skip to content

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 to represent idle meeting rooms and busy meeting rooms respectively. The idle meeting rooms \(\textit{idle}\) are sorted by index; the busy meeting rooms \(\textit{busy}\) are sorted by end time and index.

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

  • If there are busy meeting rooms with end time less than or equal to the current meeting's start time, add them to the idle meeting rooms queue \(\textit{idle}\);
  • If there are idle meeting rooms available, take the room with the smallest index from the idle queue \(\textit{idle}\) and add it to the busy queue \(\textit{busy}\);
  • If there are no idle meeting rooms, find the room with the earliest end time and smallest index from the busy queue \(\textit{busy}\), and add it back to the busy queue \(\textit{busy}\).

The time complexity is \(O(m (\log m + \log n))\), and the space complexity is \(O(n + m)\), where \(n\) and \(m\) are the number of meeting rooms and meetings respectively.

Similar problems:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort(key=lambda x: x[0])
        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])
            i = 0
            if idle:
                i = heappop(idle)
                heappush(busy, (e, i))
            else:
                time_end, i = heappop(busy)
                heappush(busy, (time_end + e - s, i))
            cnt[i] += 1
        ans = 0
        for i in range(n):
            if cnt[ans] < cnt[i]:
                ans = i
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        using pli = pair<long long, int>;
        priority_queue<pli, vector<pli>, greater<pli>> busy;
        priority_queue<int, vector<int>, greater<int>> idle;
        for (int i = 0; i < n; ++i) {
            idle.push(i);
        }
        vector<int> cnt(n);
        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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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 }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function mostBooked(n: number, meetings: number[][]): number {
    meetings.sort((a, b) => a[0] - b[0]);

    const idle = new MinPriorityQueue<number>();
    for (let i = 0; i < n; ++i) {
        idle.enqueue(i);
    }
    const busy = new PriorityQueue<[number, number]>((a, b) => {
        if (a[0] === b[0]) {
            return a[1] - b[1];
        }
        return a[0] - b[0];
    });
    const cnt: number[] = new Array(n).fill(0);
    for (const v of meetings) {
        const s = v[0],
            e = v[1];
        while (!busy.isEmpty() && busy.front()[0] <= s) {
            const i = busy.dequeue()[1];
            idle.enqueue(i);
        }
        let i = 0;
        if (!idle.isEmpty()) {
            i = idle.dequeue();
            busy.enqueue([e, i]);
        } else {
            const x = busy.dequeue();
            i = x[1];
            busy.enqueue([x[0] + e - s, i]);
        }
        ++cnt[i];
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (cnt[ans] < cnt[i]) {
            ans = i;
        }
    }
    return ans;
}

Comments