Leetcode 2402. Meeting Rooms III

[Woodyiiiiiii]

这是一道模拟题，这是我第二次遇见了，第一次是Time to cross the bridge。

这类题型的solution大体上都是利用1个或以上的Heap进行模拟。特别是这种对于时间和排队等待的类型，Heap里存的是时间。

这题不难，但我还是花了44分钟左右AC了，要加快速度，有以下注意点：

1. rooms的Heap先以时间排序，再按照索引排序；接着，要注意有多个unused rooms的情况，这时就不能简单地拿Heap的第一个了，需要建立以索引最优先的Heap来找到最小索引的rooms
2. 小细节，判断条件while (!roomsPQ.isEmpty() && roomsPQ.peek().time <= meeting[0]) {中time<=，别忘了等号，因为题目条件是半区间，所以等于meeting时间的情况下rooms还是可以用的，要加入排序
3. 一开始我在堆Heap的泛型中没想用Pair，直接用int[]，但卡在最后一个test上了，显然时间是有可能超过int最值的，所以改用long表示时间，又由于pq的comparator返回的是int，所以不能用long[]，只能用Pair

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Pair> roomsPQ = new PriorityQueue<>(new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                if (o1.time == o2.time) {
                    return o1.idx - o2.idx;
                }
                return (int) (o1.time - o2.time);
            }
        });
        for (int i = 0; i < n; ++i) {
            roomsPQ.add(new Pair(0, i, 0));
        }

        // simulate
        for (int[] meeting : meetings) {
            if (roomsPQ.peek().time >= meeting[0]) {
                Pair room = roomsPQ.poll();
                room.time += meeting[1] - meeting[0];
                room.cnt++;
                roomsPQ.add(room);
            } else {
                PriorityQueue<Pair> tmp = new PriorityQueue<>(Comparator.comparing(o -> o.idx));
                while (!roomsPQ.isEmpty() && roomsPQ.peek().time <= meeting[0]) {
                    tmp.add(roomsPQ.poll());
                }
                Pair room = tmp.poll();
                room.time = meeting[1];
                room.cnt++;
                roomsPQ.add(room);
                while (!tmp.isEmpty()) {
                    roomsPQ.add(tmp.poll());
                }
            }
        }

        int ans = -1, max = 0;
        while (!roomsPQ.isEmpty()) {
            Pair room = roomsPQ.poll();
            if (room.cnt > max) {
                max = room.cnt;
                ans = room.idx;
            } else if (room.cnt == max) {
                ans = Math.min(ans, room.idx);
            }
        }
        return ans;
    }

    class Pair {
        long time;
        int idx;
        int cnt;
        
        public Pair(long time, int idx, int cnt) {
            this.time = time;
            this.idx = idx;
            this.cnt = cnt;
        }
    }
}

类似题目：

• 2532. Time to Cross a Bridge

---

• 2402. Meeting Rooms II