2402-会议室 III

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间
[starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

  1. 每场会议都会在未占用且编号 最小 的会议室举办。
  2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
  3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间[a, b) 是 a 和 b 之间的区间， 包括 a 但 不包括 b 。

示例 1：

**输入：** n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
**输出：** 0
**解释：**
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

**输入：** n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
**输出：** 1
**解释：**
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

提示：

  • 1 <= n <= 100
  • 1 <= meetings.length <= 105
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 105
  • starti 的所有值 互不相同

本题 视频讲解 已出炉，欢迎素质三连，在评论区分享你对这场周赛的看法~

用两个小顶堆模拟：

  • idle 维护在 start}_i 时刻空闲的会议室的编号；
  • using 维护在 start}_i 时刻使用中的会议室的结束时间和编号。

这两类会议室是互补关系，伴随着会议的开始和结束，会议室在这两类中来回倒。

对 meetings 按照开始时间排序，然后遍历 meetings，按照题目要求模拟即可，具体模拟方式见代码。

复杂度分析

  • 时间复杂度：O(n+m(\log n + \log m))，其中 m 为 meetings 的长度。注意每个会议至多入堆出堆各一次。
  • 空间复杂度：O(n)。

相似题目

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        cnt = [0] * n
        idle, using = list(range(n)), []
        meetings.sort(key=lambda m: m[0])
        for st, end in meetings:
            while using and using[0][0] <= st:
                heappush(idle, heappop(using)[1])  # 维护在 st 时刻空闲的会议室
            if len(idle) == 0:
                e, i = heappop(using)  # 没有可用的会议室，那么弹出一个最早结束的会议室（若有多个同时结束的，会弹出下标最小的）
                end += e - st  # 更新当前会议的结束时间
            else:
                i = heappop(idle)
            cnt[i] += 1
            heappush(using, (end, i))  # 使用一个会议室
        ans = 0
        for i, c in enumerate(cnt):
            if c > cnt[ans]:
                ans = i
        return ans
[sol1-Java]
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
class Solution {
    public int mostBooked(int n, int[][] meetings) {
        var cnt = new int[n];
        var idle = new PriorityQueue<Integer>();
        for (var i = 0; i < n; ++i) idle.offer(i);
        var using = new PriorityQueue<Pair<Long, Integer>>((a, b) -> !Objects.equals(a.getKey(), b.getKey()) ? Long.compare(a.getKey(), b.getKey()) : Integer.compare(a.getValue(), b.getValue()));
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
        for (var m : meetings) {
            long st = m[0], end = m[1];
            while (!using.isEmpty() && using.peek().getKey() <= st) {
                idle.offer(using.poll().getValue()); // 维护在 st 时刻空闲的会议室
            }
            int id;
            if (idle.isEmpty()) {
                var p = using.poll(); // 没有可用的会议室，那么弹出一个最早结束的会议室（若有多个同时结束的，会弹出下标最小的）
                end += p.getKey() - st; // 更新当前会议的结束时间
                id = p.getValue();
            } else id = idle.poll();
            ++cnt[id];
            using.offer(new Pair<>(end, id)); // 使用一个会议室
        }
        var ans = 0;
        for (var i = 0; i < n; ++i) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
}
[sol1-C++]
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
class Solution {
public:
    int mostBooked(int n, vector<vector<int>> &meetings) {
        int cnt[n]; memset(cnt, 0, sizeof(cnt));
        priority_queue<int, vector<int>, greater<>> idle;
        for (int i = 0; i < n; ++i) idle.push(i);
        priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> using_;
        sort(meetings.begin(), meetings.end(), [](auto &a, auto &b) { return a[0] < b[0]; });
        for (auto &m : meetings) {
            long st = m[0], end = m[1], id;
            while (!using_.empty() && using_.top().first <= st) {
                idle.push(using_.top().second); // 维护在 st 时刻空闲的会议室
                using_.pop();
            }
            if (idle.empty()) {
                auto[e, i] = using_.top(); // 没有可用的会议室，那么弹出一个最早结束的会议室（若有多个同时结束的，会弹出下标最小的）
                using_.pop();
                end += e - st; // 更新当前会议的结束时间
                id = i;
            } else {
                id = idle.top();
                idle.pop();
            }
            ++cnt[id];
            using_.emplace(end, id); // 使用一个会议室
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
};
[sol1-Go]
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
func mostBooked(n int, meetings [][]int) (ans int) {
	cnt := make([]int, n)
	idle := hp{make([]int, n)}
	for i := 0; i < n; i++ {
		idle.IntSlice[i] = i
	}
	using := hp2{}
	sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
	for _, m := range meetings {
		st, end := m[0], m[1]
		for len(using) > 0 && using[0].end <= st {
			heap.Push(&idle, heap.Pop(&using).(pair).i) // 维护在 st 时刻空闲的会议室
		}
		var i int
		if idle.Len() == 0 {
			p := heap.Pop(&using).(pair) // 没有可用的会议室，那么弹出一个最早结束的会议室（若有多个同时结束的，会弹出下标最小的）
			end += p.end - st // 更新当前会议的结束时间
			i = p.i
		} else {
			i = heap.Pop(&idle).(int)
		}
		cnt[i]++
		heap.Push(&using, pair{end, i}) // 使用一个会议室
	}
	for i, c := range cnt {
		if c > cnt[ans] {
			ans = i
		}
	}
	return
}

type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{}   { 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 interface{}) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
 Comments
On this page
2402-会议室 III