2402.会议室III

目标

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

1. 每场会议都会在未占用且编号 最小 的会议室举办。
2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [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 <= 100
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 10^5
• starti 的所有值 互不相同

思路

有 n 个会议室，编号为 0 ~ n - 1。有一个二维数组，meetings[i] 表示 [starti, endi) 范围内需要举办一场会议，会优先使用未被占用且编号最小的会议室。如果没有会议室可用，则需要延后举办，如果同一时间有多个会议需要举办，原开始时间最小的优先举办。

这个题目的关键点是，当有多个满足条件的会议室时，选择编号最小的，而不是最早可用的。需要使用两个优先队列，一个追踪会议室的最早空闲时间，另一个则追踪空闲会议室中编号最小的。将会议按照开始时间排序，按顺序遍历，将可选的会议室加入空闲编号堆，如果这个堆非空，从中取一个会议室，并将结束时间（可用时间）放入空闲时间堆中；否则，从空闲时间堆中取一个会议室，将其空闲时间加上会议持续时间后再放入堆中。

代码

/**
 * @date 2025-12-30 14:01
 */
public class MostBooked2402 {

    public int mostBooked(int n, int[][] meetings) {
        int[] cnt = new int[n];
        PriorityQueue<int[]> rooms = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return a[1] - b[1];
        });
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int i = 0; i < n; i++) {
            rooms.offer(new int[]{0, i});
        }
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        for (int[] meeting : meetings) {
            while (!rooms.isEmpty() && rooms.peek()[0] <= meeting[0]) {
                q.offer(rooms.poll());
            }
            int[] room;
            if (!q.isEmpty()) {
                room = q.poll();
                rooms.offer(new int[]{meeting[1], room[1]});
            } else {
                room = rooms.poll();
                rooms.offer(new int[]{room[0] + meeting[1] - meeting[0], room[1]});
            }
            cnt[room[1]]++;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (cnt[i] > cnt[res]) {
                res = i;
            }
        }
        return res;
    }

}

性能