23-05-20 总结 Meeting rooms 系列3个题目

标签：sort 20 23 int 05 PriorityQueue time minHeap meeting

题目列表：

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次。

标签：sort,20,23,int,05,PriorityQueue,time,minHeap,meeting
From： https://www.cnblogs.com/xianzhon/p/17416861.html