题目列表：
- P1. 【easy，会员】Meeting Rooms - LeetCode
- P2. 【Mid，会员】Meeting Rooms II - LeetCode
- P3. Meeting Rooms III - LeetCode
P1. 会员题，检测会议是否安排得开
思路：
- 非常简单，直接按start time进行排序，然后检测是否有overlap即可
- 时间：O(nlog n)，空间:O(1)
class Solution {
public boolean canAttendMeetings(int[][] A) {
if (A.length == 0) return true;
// just sort the array according to start time
Arrays.sort(A, (a, b) -> Integer.compare(a[0], b[0]));
int prevEnd = -1;
for (int[] meeting : A) {
if (meeting[0] < prevEnd) {
return false;
}
prevEnd = meeting[1];
}
return true;
}
}
P2 求需要多少间会议室
解法1：优先队列 - O(n logn)
思路：
-
之前做过，这个直接模拟真实场景的会议室安排算法。对会议的开始时间升序排列，开始时间相同的，按照结束时间升序排列。依次分配会议室，同时维护一个已分配的会议室列表，对于第i个会议，在给它分配会议室前，看之前是否有会议结束了。如果有会议在它之前结束，那就不需要再分配新会议室。没有，则需要分配一间新会议室。在这个过程中，维护的当前的会议室列表，最大长度就是所需要的会议室的数量。
-
那么怎么知道当前会议，在此之前，是否有会议结束呢？直观的做法是维护一个会议室的列表，按结束时间排序，如果最前面的会议室，它的结束时间小于当前的会议开始时间，则意味着有空闲的会议室了。为了快速找到一个列表中，最小的元素，我们可以使用小根堆来做，java中使用PriorityQueue类。
-
复杂度分析：
- 时间：O(n log n). 排序所有会议，O(nlogn), 优先队列保存在线的会议，每个会议进入队列一次，出去一次，所以时间复杂度是O(nlogn)
- 空间：O(n). 使用了优先队列，最多保存n个元素，O(n)。
class Solution {
public int minMeetingRooms(int[][] A) {
Arrays.sort(A, (a, b) -> {
if (a[0] != b[0]) {
return Integer.compare(a[0], b[0]);
}
return Integer.compare(a[1], b[1]);
});
// store the end time of meeting which were assigned meeting room
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int ans = 0;
for(int[] meeting : A) {
// check if there is any meeting room available
while (!minHeap.isEmpty() && minHeap.peek() <= meeting[0]) {
minHeap.poll();
}
// assign a meeting room either new or reuse old one
minHeap.offer(meeting[1]);
// update the maximum live meeting room number
ans = Math.max(ans, minHeap.size());
}
return ans;
}
}
好像不用针对end time进行排序也可以，只按照start time排序，不知道是否是test case miss。需要再此思考一下，想清楚。【TODO】
class Solution {
public int minMeetingRooms(int[][] A) {
Arrays.sort(A, (a, b) -> Integer.compare(a[0], b[0]));
// store the end time of meeting which were assigned meeting room
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
int ans = 0;
for(int[] meeting : A) {
// check if there is any meeting room available
while (!minHeap.isEmpty() && minHeap.peek() <= meeting[0]) {
minHeap.poll();
}
// assign a meeting room either new or reuse old one
minHeap.offer(meeting[1]);
// update the maximum live meeting room number
ans = Math.max(ans, minHeap.size());
}
return ans;
}
}
看了题解，更好的做法是，在考虑第i个会议时，不需要把所有的结束的会议都清理掉，只看最早结束的一个就可以了，然后最后剩下的队列大小就是会议室的个数。【best】
class Solution {
public int minMeetingRooms(int[][] A) {
Arrays.sort(A, (a, b) -> Integer.compare(a[0], b[0]));
// store the end time of meeting which were assigned meeting room
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for(int[] meeting : A) {
// check if there is any meeting room available
if (!minHeap.isEmpty() && minHeap.peek() <= meeting[0]) {
minHeap.poll();
}
// assign a meeting room either new or reuse old one
minHeap.offer(meeting[1]);
}
return minHeap.size();
}
}
实现细节：for循环里，也可以使用index-based, 先把第一个会议的结束时间加到minHeap，然后再遍历剩下的n-1个会议。
思考：这题是否可以使用Sweep line思路来做？可以，但是需要特别注意排序points的顺序。
解法2： SweepLine - O(n logn)
class Solution {
public int minMeetingRooms(int[][] A) {
int n = A.length;
int[][] points = new int[2*n][2];
// Sweep line
for(int i = 0, j = 0; i < n; i++, j++) {
points[j][0] = A[i][0];
points[j][1] = -1; // start point
points[++j][0] = A[i][1];
points[j][1] = 1; // end point;
}
// sort according to time
Arrays.sort(points, (a, b) -> { // 这里的排序很关键
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(b[1], a[1]);
});
// check each time point
int count = 0, ans = 0;
for(int[] point : points) {
if (point[1] == -1) {
count++;
} else {
count--;
}
ans = Math.max(ans, count);
}
return ans;
}
}
排序很关键，如果只按time排序，那么案例：[[13,15],[1,13]]会返回2，正确答案是1。然后如果时间相同，先按照start，再按end，上述案例同样返回2。正确的是先按时间升序排列，然后按照结束、开始排列。一个会议结束了，count-1，下一个会议就可以利用这个会议室了。
复杂度分析：
- 时间：O(nlogn) 总共是2n个point，排序O(nlogn)，后面遍历每个点，O(n)
- 空间：O(n)
P3 III. 求预定最多的会议室
题目描述：LeetCode - The World's Leading Online Programming Learning Platform
我的第一个版本：思路：
- use a minHeap to track the end time of live meeting (also need to store the roomId)
- use a TreeSet to track the available meeting rooms, and we use small index first, so it needs to be sorted. And support getting minValue, and insert operation. 【思考：这里是否也可以使用PriorityQueue? 我看讨论区有提到两个PQ，可以！】
class Solution {
public int mostBooked(int n, int[][] meetings) {
// sort meetings according to start time, simulate real meeting arrangement
Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
// track available meeting rooms
TreeSet<Integer> availableRooms = new TreeSet<>();
int[] bookCounts = new int[n];
for(int i = 0; i < n; i++) {
availableRooms.add(i);
}
// track the end time of each live meetings (endTime, roomIdx)
PriorityQueue<long[]> minHeap = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Long.compare(a[0], b[0]); // sort by end time asc
return Long.compare(a[1], b[1]); // sort by roomIdx asc
});
// arrangement
for(int[] meeting : meetings) {
long start = meeting[0], end = meeting[1];
// check if there is any meeting ending
while (!minHeap.isEmpty() && minHeap.peek()[0] <= start) {
int roomId = (int)minHeap.poll()[1];
availableRooms.add(roomId);
}
// delay meeting, until first meeting room available (i.e. end time shortest)
if (availableRooms.isEmpty()) {
long[] cur = minHeap.poll();
availableRooms.add((int)cur[1]);
// delay the meeting
end = (end - start) + cur[0];
start = cur[0];
}
int roomId = availableRooms.first();
availableRooms.remove(roomId);
bookCounts[roomId]++;
minHeap.offer(new long[] {end, roomId});
}
// find most booked meeting room
int ans = 0;
for(int i = 1; i < n; i++) {
if (bookCounts[i] > bookCounts[ans]) {
ans = i;
}
}
return ans;
}
}
复杂度分析：
- 时间： O(n + m logn). m个meeting。track meeting room book count, O(n). first sort meetings according to start time, which is O(m logm), each meeting will enter the pq only once, and poll once, each offer/poll operation of heap is O(log n), the heap at most contains n items. The total time is O(n + m logn)
- 空间：O(n). use array to track room booked count: O(n), use minHeap to track meeting end time, at most n meetings be held at same time, so heap max size is O(n).
版本2：小改动，使用两个PriorityQueue，替换了上面版本1的TreeSet，操作稍微简化了一点点 (TreeSet.first() + remove(x)，直接用pq.poll()即可)
class Solution {
public int mostBooked(int n, int[][] meetings) {
// sort meetings according to start time, simulate real meeting arrangement
Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
// track available meeting rooms
PriorityQueue<Integer> availableRooms = new PriorityQueue<>();
int[] bookCounts = new int[n];
for(int i = 0; i < n; i++) {
availableRooms.offer(i);
}
// track the end time of each live meetings (endTime, roomIdx)
PriorityQueue<long[]> minHeap = new PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Long.compare(a[0], b[0]); // sort by end time asc
return Long.compare(a[1], b[1]); // sort by roomIdx asc
});
// arrangement
for(int[] meeting : meetings) {
long start = meeting[0], end = meeting[1];
// check if there is any meeting ending
while (!minHeap.isEmpty() && minHeap.peek()[0] <= start) {
int roomId = (int)minHeap.poll()[1];
availableRooms.offer(roomId);
}
// delay meeting, until first meeting room available (i.e. end time shortest)
if (availableRooms.isEmpty()) {
long[] cur = minHeap.poll();
availableRooms.offer((int)cur[1]);
// delay the meeting
end = (end - start) + cur[0];
start = cur[0];
}
int roomId = availableRooms.poll();
bookCounts[roomId]++;
minHeap.offer(new long[] {end, roomId});
}
// find most booked meeting room
int ans = 0;
for(int i = 1; i < n; i++) {
if (bookCounts[i] > bookCounts[ans]) {
ans = i;
}
}
return ans;
}
}
时间复杂度分析几乎不变，因为PQ的每次操作时间复杂度也是O(log n)，最多有n个room空闲。最多offer操作n+m次。