前言：

这是来自likou的一道算法题，使用双堆模拟解法

这是一个会议室资源调度问题，核心是按照特定规则将会议分配给会议室，需要考虑延期机制和优先级。

---

题目：

给你一个整数 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 <= 105
meetings[i].length == 2
0 <= starti < endi <= 5 * 105
starti 的所有值 互不相同

---

题目分析：

核心挑战:

1. 处理延期会议：哪些会议在等待
2. 维护会议室状态：哪些会议室空闲，何时释放
3. 优先级排序：延期会议按原开始时间排序
4. 时间推进：模拟整个时间线上的事件

---

事件驱动：

关注会议室释放时间和会议开始时间

数据结构选择：

1. 维护空闲会议室（优先选择编号小的）
2. 维护进行中的会议（知道何时结束）
3. 维护等待队列（按原开始时间排序）

时间推进策略：

跳到下一个关键时间点（会议开始或会议室释放）

---

算法逻辑框架

1. 按原开始时间排序所有会议
2. 初始化所有会议室为空闲
3. 按时间顺序处理
4. 统计每个会议室的会议次数
5. 返回举办会议次数最多且编号最小的会议室

---

代码：

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings,(a,b) -> a[0] - b[0]);

        PriorityQueue<Integer> freerooms = new PriorityQueue<>();
        for(int i = 0;i<n;i++){
            freerooms.offer(i);
        }

        PriorityQueue<long[]>  using = new PriorityQueue<>(
            (a,b) ->a[0] != b[0] ? Long.compare(a[0],b[0]) : Long.compare(a[1],b[1])
        );

        int[] cnt = new int[n];

        for(int[] m : meetings){
            long start = m[0];
            long end = m[1];

            while(!using.isEmpty() && using.peek()[0] <= start){
                freerooms.offer((int) using.poll()[1]);
            }

            int i;
            if(!freerooms.isEmpty()){
                i = freerooms.poll();
            }else{
                long[] p = using.poll();
                end += p[0] - start;
                i = (int) p[1];
            }

            using.offer(new long[]{end,i});
            cnt[i]++;
        } 
        int ans = 0;
        for(int i = 1;i<n;i++){
            if(cnt[i] > cnt[ans]){
                ans = i;
            }
        }
        return ans;
    }
}

---

代码分析：

1、排序

对meetings进行排序，以开始时间的高低排序

Arrays.sort(meetings,(a,b) -> a[0] - b[0]);

2、初始化

定义两个队列（堆），队列freerooms来存空闲的会议室编号，并初始化，队列using来存使用的会议室编号，并且存的数组（结束时间，会议室编号）

PriorityQueue<Integer> freerooms = new PriorityQueue<>();
    for(int i = 0;i<n;i++){
        freerooms.offer(i);
    }

PriorityQueue<long[]>  using = new PriorityQueue<>((a,b) ->a[0] != b[0] ? Long.compare(a[0],b[0]) : Long.compare(a[1],b[1]));

3、逻辑实现

int[] cnt = new int[n];

for(int[] m : meetings){
    long start = m[0];
    long end = m[1];

    while(!using.isEmpty() && using.peek()[0] <= start){
        freerooms.offer((int) using.poll()[1]);
    }
    int i;
    if(!freerooms.isEmpty()){
        i = freerooms.poll();
    }else{
        long[] p = using.poll();
        end += p[0] - start;
        i = (int) p[1];
    }

    using.offer(new long[]{end,i});
    cnt[i]++;
} 

1、在start时刻空闲的会议室

如果在使用的会议室里面存在结束时间小于当前的开始时间，则需要踢出队列，并把这个会议室加入到空闲会议室队列

while(!using.isEmpty() && using.peek()[0] <= start){
    freerooms.offer((int) using.poll()[1]);
}

2、判断

如果空闲会议室队列不为空，就说明里面有会议室可以使用，就取最小的会议室供后面使用

如果为空，就说明没有空闲的会议室，则弹出一个最早结束的会议室供使用，并调整结束时间

    int i;
    if(!freerooms.isEmpty()){
        i = freerooms.poll();
    }else{
        long[] p = using.poll();
        end += p[0] - start;
        i = (int) p[1];
    }

3、提交，并记录

把这个会议室加入队列，并把这个会议室的使用次数加1

    using.offer(new long[]{end,i});
    cnt[i]++;

4、循环找最小值

循环meetings，得到cnt数组，各个会议室的使用次数，这个时候循环比较，得到使用次数最多的那间会议室

int ans = 0;
for(int i = 1;i<n;i++){
    if(cnt[i] > cnt[ans]){
        ans = i;
    }
}

---

结语：

这是一个很经典的双堆模拟问题，来自力扣，希望对你有帮助！