Hard

题目描述

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

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

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

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

返回举行最多次会议的房间 编号 。如果存在多个房间都举行了最多次会议，那么返回编号 最小 的房间。

示例 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) 。
会议室 0 举行了 1 场会议，会议室 1 和 2 都举行了 2 场会议，所以返回 1 。

提示：

  • 1 <= n <= 100
  • 1 <= meetings.length <= 10^5
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 10^5
  • 所有 starti 的值 互不相同

解题思路

这道题需要模拟会议室分配过程，核心思路是使用两个优先队列进行管理。

解题思路：

  1. 排序预处理：首先按照会议开始时间对所有会议进行排序，确保按时间顺序处理。

  2. 双堆管理：

    • available：小根堆，存储当前可用的会议室编号，确保优先使用编号最小的房间
    • busy：小根堆，存储正在使用的会议室信息 (结束时间, 房间编号)，按结束时间排序

  3. 模拟分配过程：

    • 对于每个会议，首先检查是否有会议室在当前时间已经结束，将这些房间释放到 available 中
    • 如果有可用房间，直接分配编号最小的房间
    • 如果没有可用房间，找到最早结束的房间，延迟当前会议到该房间空闲时开始

  4. 统计和返回：使用数组记录每个房间举行的会议次数，最后返回次数最多且编号最小的房间。

时间复杂度：排序需要 O(m log m)，每个会议的处理涉及堆操作，总体为 O(m log n)，其中 m 是会议数量。

空间复杂度：需要 O(n) 的额外空间存储堆和计数数组。

代码实现

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        
        priority_queue<int, vector<int>, greater<int>> available;
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> busy;
        vector<int> count(n, 0);
        
        for (int i = 0; i < n; i++) {
            available.push(i);
        }
        
        for (auto& meeting : meetings) {
            long long start = meeting[0];
            long long duration = meeting[1] - meeting[0];
            
            while (!busy.empty() && busy.top().first <= start) {
                available.push(busy.top().second);
                busy.pop();
            }
            
            if (!available.empty()) {
                int room = available.top();
                available.pop();
                count[room]++;
                busy.push({start + duration, room});
            } else {
                auto [endTime, room] = busy.top();
                busy.pop();
                count[room]++;
                busy.push({endTime + duration, room});
            }
        }
        
        int maxCount = 0, result = 0;
        for (int i = 0; i < n; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                result = i;
            }
        }
        
        return result;
    }
};

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        
        available = list(range(n))
        heapq.heapify(available)
        busy = []
        count = [0] * n
        
        for start, end in meetings:
            duration = end - start
            
            while busy and busy[0][0] <= start:
                _, room = heapq.heappop(busy)
                heapq.heappush(available, room)
            
            if available:
                room = heapq.heappop(available)
                count[room] += 1
                heapq.heappush(busy, (start + duration, room))
            else:
                end_time, room = heapq.heappop(busy)
                count[room] += 1
                heapq.heappush(busy, (end_time + duration, room))
        
        max_count = max(count)
        return count.index(max_count)

public class Solution {
    public int MostBooked(int n, int[][] meetings) {
        Array.Sort(meetings, (a, b) => a[0].CompareTo(b[0]));
        
        var available = new PriorityQueue<int, int>();
        var busy = new PriorityQueue<(long endTime, int room), long>();
        var count = new int[n];
        
        for (int i = 0; i < n; i++) {
            available.Enqueue(i, i);
        }
        
        foreach (var meeting in meetings) {
            long start = meeting[0];
            long duration = meeting[1] - meeting[0];
            
            while (busy.Count > 0 && busy.Peek().endTime <= start) {
                var (_, room) = busy.Dequeue();
                available.Enqueue(room, room);
            }
            
            if (available.Count > 0) {
                int room = available.Dequeue();
                count[room]++;
                busy.Enqueue((start + duration, room), start + duration);
            } else {
                var (endTime, room) = busy.Dequeue();
                count[room]++;
                busy.Enqueue((endTime + duration, room), endTime + duration);
            }
        }
        
        int maxCount = 0, result = 0;
        for (int i = 0; i < n; i++) {
            if (count[i] > maxCount) {
                maxCount = count[i];
                result = i;
            }
        }
        
        return result;
    }
}

var mostBooked = function(n, meetings) {
    meetings.sort((a, b) => a[0] - b[0]);
    
    const available = new MinPriorityQueue({ priority: x => x });
    const busy = new MinPriorityQueue({ priority: x => x[0] });
    const count = new Array(n).fill(0);
    
    for (let i = 0; i < n; i++) {
        available.enqueue(i);
    }
    
    for (const [start, end] of meetings) {
        const duration = end - start;
        
        while (!busy.isEmpty() && busy.front().element[0] <= start) {
            const [_, room] = busy.dequeue().element;
            available.enqueue(room);
        }
        
        if (!available.isEmpty()) {
            const room = available.dequeue().element;
            count[room]++;
            busy.enqueue([start + duration, room]);
        } else {
            const [endTime, room] = busy.dequeue().element;
            count[room]++;
            busy.enqueue([endTime + duration, room]);
        }
    }
    
    let maxCount = 0, result = 0;
    for (let i = 0; i < n; i++) {
        if (count[i] > maxCount) {
            maxCount = count[i];
            result = i;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m log m + m log n)排序需要 O(m log m)，每个会议处理需要 O(log n) 的堆操作
空间复杂度O(n)需要存储可用房间堆、忙碌房间堆和计数数组

相关题目