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] = [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:
- Each meeting will take place in the unused room with the lowest number.
- 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.
- 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 \leq n \leq 100$
$1 \leq meetings.length \leq {10}^{5}$
$meetings[i].length == 2$
$0 \leq {start}_i < {end}_i \leq 5 \times {10}^{5}$
All the values of starti are unique.
解题思路
当时比赛的时候想到用堆来维护每个会议室的待开始时间，当时的堆是存储两个关键字，第一个关键字是待开始时间，第二个关键字是会议室编号。然后优先得到结束时间考前的会议室，但当时没有意识到一种情况，比如说现在某个会议的开始时间是$10$，当前堆中有两个会议室，一个会议室的关键字为$\{ {5, 0} \}$，另一个会议室的关键字为$\{ {0, 1} \}$，如果按照上面描述来执行的话会弹出$\{ {0, 1} \}$这个会议室，但事实上正确的答案是$\{ {5, 0} \}$这个会议室。
然后看了眼数据范围，会议室数量最大值为$100$，因此直接暴力模拟也可以过，时间复杂度为$O(n \times m)$，试了一下还真过了，计算量为${10}^{7}$级别。
正解是开两个堆来维护，时间复杂度可以做到$nlogm$，因此$m$的取值范围可以扩大到${10}^{5}$。
一个堆是维护空闲的会议室，关键字为会议室的编号。另外一个堆用来维护待开始时间最小的会议室，两个关键字，第一个是待开始时间，第二个是会议室编号。
流程是对于某场会议，开始时间的是$a$，先在第二个堆中把所有待开始时间小于等于$a$的会议加到第一个堆中。然后如果第一个堆中存在元素，则堆顶元素就是最优的会议室。否则在第二个堆中的堆顶元素是最优的会议室（此时第一个堆为空意味着所有的会议室处于忙碌状态，需要等到第一个结束的会议室）。
AC代码如下：
1 class Solution {
2 public:
3 int mostBooked(int n, vector<vector<int>>& meetings) {
4 sort(meetings.begin(), meetings.end());
5 priority_queue<int, vector<int>, greater<int>> pq1;
6 priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq2; // 会爆int
7 for (int i = 0; i < n; i++) { // 初始时所有会议室为空
8 pq1.push(i);
9 }
10
11 vector<int> cnt(n);
12 for (auto &p : meetings) {
13 while (!pq2.empty() && pq2.top().first <= p[0]) { // 不可以写成if
14 pq1.push(pq2.top().second);
15 pq2.pop();
16 }
17 if (!pq1.empty()) {
18 cnt[pq1.top()]++;
19 pq2.push({p[1], pq1.top()});
20 pq1.pop();
21 }
22 else {
23 cnt[pq2.top().second]++;
24 pq2.push({p[1] + pq2.top().first - p[0], pq2.top().second});
25 pq2.pop();
26 }
27 }
28
29 return max_element(cnt.begin(), cnt.end()) - cnt.begin();
30 }
31 };
参考资料
力扣第309场周赛：https://www.bilibili.com/video/BV1DB4y1G7gX
标签：10,room,III,meetings,meeting,Rooms,time,Meeting,rooms From： https://www.cnblogs.com/onlyblues/p/16660030.html