class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
}
};
2402. 会议室 III
给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。
给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。
会议将会按以下方式分配给会议室：
返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。
半闭区间 [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 <= 1001 <= meetings.length <= 105meetings[i].length == 20 <= starti < endi <= 5 * 105starti 的所有值 互不相同原站题解
python3 解法, 执行用时: 2668 ms, 内存消耗: 50.1 MB, 提交时间: 2023-06-17 09:12:49
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
cnt, t = [0] * n, [0] * n
for [s, e] in sorted(meetings):
t = list(map(lambda x : max(x, s), t))
choice = t.index(min(t))
t[choice], cnt[choice] = t[choice] + e - s, cnt[choice] + 1
return cnt.index(max(cnt))
python3 解法, 执行用时: 320 ms, 内存消耗: 50.3 MB, 提交时间: 2023-06-17 09:12:06
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
golang 解法, 执行用时: 260 ms, 内存消耗: 17.4 MB, 提交时间: 2023-06-17 09:11:47
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 }
java 解法, 执行用时: 102 ms, 内存消耗: 92.2 MB, 提交时间: 2023-06-17 09:11:35
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;
}
}
cpp 解法, 执行用时: 396 ms, 内存消耗: 94.5 MB, 提交时间: 2023-06-17 09:11:24
/**
* 双堆模拟
* idle 维护在 starti 时刻空闲的会议室的编号；
* using 维护在 starti 时刻使用中的会议室的结束时间和编号。
**/
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;
}
};