LeetCode第253题：会议室II

题目描述

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2
解释：需要两个会议室
- 会议室1：[0,30]
- 会议室2：[5,10], [15,20]

示例 2：

输入：intervals = [[7,10],[2,4]]
输出：1
解释：只需要一个会议室就足够了
- 会议室1：[2,4], [7,10]

提示

• 1 <= intervals.length <= 10^4
• 0 <= starti < endi <= 10^6

解题思路

方法一：扫描线算法

扫描线算法是处理区间问题的经典方法。我们可以把每个会议的开始时间和结束时间看作是时间轴上的两个事件：开始时间需要一个新的会议室，结束时间释放一个会议室。

关键点

• 将所有会议的开始时间和结束时间分别提取出来，并分别排序
• 使用两个指针遍历排序后的开始时间和结束时间
• 当遇到开始时间时，需要一个新的会议室，当遇到结束时间时，释放一个会议室
• 记录遍历过程中所需的最大会议室数量

具体步骤

1. 提取所有会议的开始时间和结束时间，分别存入两个数组
2. 对开始时间数组和结束时间数组分别排序
3. 使用两个指针 i 和 j 分别遍历开始时间和结束时间数组
4. 比较当前指针指向的开始时间和结束时间：
   • 如果开始时间早于结束时间，说明需要一个新的会议室，将房间计数加1，移动开始时间指针
   • 如果结束时间早于或等于开始时间，说明可以释放一个会议室，将房间计数减1，移动结束时间指针
5. 记录遍历过程中房间计数的最大值，即为所需的最小会议室数量

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是会议的数量。排序需要 O(n log n) 的时间，遍历需要 O(2n) = O(n) 的时间。
• 空间复杂度：O(n)，需要额外的数组存储所有会议的开始时间和结束时间。

方法二：优先队列（最小堆）

另一种思路是使用优先队列（最小堆）来跟踪当前正在进行的会议的结束时间。

关键点

• 按照会议的开始时间对会议进行排序
• 使用优先队列（最小堆）存储当前正在进行的会议的结束时间
• 遍历排序后的会议，对于每个会议：
  • 移除所有在当前会议开始前已经结束的会议
  • 将当前会议的结束时间加入优先队列
• 优先队列的最大大小即为所需的最小会议室数量

具体步骤

1. 按照会议的开始时间对会议进行排序
2. 创建一个优先队列（最小堆），用于存储当前正在进行的会议的结束时间
3. 遍历排序后的会议：
   • 移除优先队列中所有结束时间早于或等于当前会议开始时间的会议
   • 将当前会议的结束时间加入优先队列
4. 优先队列的最大大小即为所需的最小会议室数量

复杂度分析

• 时间复杂度：O(n log n)，其中 n 是会议的数量。排序需要 O(n log n) 的时间，每次插入和删除堆操作都需要 O(log n) 的时间，总共有 n 次操作。
• 空间复杂度：O(n)，优先队列最多可能包含 n 个元素。

图解思路

方法一：扫描线算法分析表

时间点	事件类型	当前会议室数量	最大会议室数量	说明
0	开始	1	1	会议 [0,30] 开始，需要1个会议室
5	开始	2	2	会议 [5,10] 开始，需要2个会议室
10	结束	1	2	会议 [5,10] 结束，释放1个会议室
15	开始	2	2	会议 [15,20] 开始，需要2个会议室
20	结束	1	2	会议 [15,20] 结束，释放1个会议室
30	结束	0	2	会议 [0,30] 结束，释放1个会议室

方法二：优先队列分析表

当前会议	优先队列（结束时间）	需要的会议室数量	说明
[0,30]	[30]	1	第一个会议需要1个会议室
[5,10]	[10,30]	2	第二个会议与第一个重叠，需要2个会议室
[15,20]	[20,30]	2	第三个会议开始前，第二个已结束，复用该会议室

代码实现

C# 实现

public class Solution {
    // 方法一：扫描线算法
    public int MinMeetingRooms1(int[][] intervals) {
        int n = intervals.Length;
        int[] startTimes = new int[n];
        int[] endTimes = new int[n];
        
        // 提取开始时间和结束时间
        for (int i = 0; i < n; i++) {
            startTimes[i] = intervals[i][0];
            endTimes[i] = intervals[i][1];
        }
        
        // 对开始时间和结束时间排序
        Array.Sort(startTimes);
        Array.Sort(endTimes);
        
        int rooms = 0; // 当前使用的会议室数量
        int maxRooms = 0; // 历史最大会议室数量
        int startPtr = 0; // 开始时间指针
        int endPtr = 0; // 结束时间指针
        
        // 扫描线算法
        while (startPtr < n && endPtr < n) {
            if (startTimes[startPtr] < endTimes[endPtr]) {
                // 需要一个新的会议室
                rooms++;
                startPtr++;
            } else {
                // 释放一个会议室
                rooms--;
                endPtr++;
            }
            // 更新最大会议室数量
            maxRooms = Math.Max(maxRooms, rooms);
        }
        
        return maxRooms;
    }
    
    // 方法二：优先队列（最小堆）
    public int MinMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) {
            return 0;
        }
        
        // 按开始时间排序
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        
        // 创建最小堆，用于存储会议的结束时间
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
        
        // 处理第一个会议
        minHeap.Enqueue(intervals[0][1], intervals[0][1]);
        
        // 处理剩余会议
        for (int i = 1; i < intervals.Length; i++) {
            // 当前会议的开始时间大于等于最早结束的会议时间，可以复用会议室
            if (intervals[i][0] >= minHeap.Peek()) {
                minHeap.Dequeue(); // 移除已结束的会议
            }
            
            // 添加当前会议的结束时间
            minHeap.Enqueue(intervals[i][1], intervals[i][1]);
        }
        
        // 堆中的元素数量即为所需的会议室数量
        return minHeap.Count;
    }
}

Python 实现

import heapq

class Solution:
    # 方法一：扫描线算法
    def minMeetingRooms1(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        # 提取开始时间和结束时间
        start_times = [interval[0] for interval in intervals]
        end_times = [interval[1] for interval in intervals]
        
        # 对开始时间和结束时间排序
        start_times.sort()
        end_times.sort()
        
        rooms = 0  # 当前使用的会议室数量
        max_rooms = 0  # 历史最大会议室数量
        start_ptr = 0  # 开始时间指针
        end_ptr = 0  # 结束时间指针
        n = len(intervals)
        
        # 扫描线算法
        while start_ptr < n and end_ptr < n:
            if start_times[start_ptr] < end_times[end_ptr]:
                # 需要一个新的会议室
                rooms += 1
                start_ptr += 1
            else:
                # 释放一个会议室
                rooms -= 1
                end_ptr += 1
            # 更新最大会议室数量
            max_rooms = max(max_rooms, rooms)
        
        return max_rooms
    
    # 方法二：优先队列（最小堆）
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        # 按开始时间排序
        intervals.sort(key=lambda x: x[0])
        
        # 创建最小堆，用于存储会议的结束时间
        min_heap = []
        
        # 处理第一个会议
        heapq.heappush(min_heap, intervals[0][1])
        
        # 处理剩余会议
        for i in range(1, len(intervals)):
            # 当前会议的开始时间大于等于最早结束的会议时间，可以复用会议室
            if intervals[i][0] >= min_heap[0]:
                heapq.heappop(min_heap)  # 移除已结束的会议
            
            # 添加当前会议的结束时间
            heapq.heappush(min_heap, intervals[i][1])
        
        # 堆中的元素数量即为所需的会议室数量
        return len(min_heap)

C++ 实现

class Solution {
public:
    // 方法一：扫描线算法
    int minMeetingRooms1(vector<vector<int>>& intervals) {
        int n = intervals.size();
        if (n == 0) return 0;
        
        vector<int> startTimes(n);
        vector<int> endTimes(n);
        
        // 提取开始时间和结束时间
        for (int i = 0; i < n; i++) {
            startTimes[i] = intervals[i][0];
            endTimes[i] = intervals[i][1];
        }
        
        // 对开始时间和结束时间排序
        sort(startTimes.begin(), startTimes.end());
        sort(endTimes.begin(), endTimes.end());
        
        int rooms = 0; // 当前使用的会议室数量
        int maxRooms = 0; // 历史最大会议室数量
        int startPtr = 0; // 开始时间指针
        int endPtr = 0; // 结束时间指针
        
        // 扫描线算法
        while (startPtr < n && endPtr < n) {
            if (startTimes[startPtr] < endTimes[endPtr]) {
                // 需要一个新的会议室
                rooms++;
                startPtr++;
            } else {
                // 释放一个会议室
                rooms--;
                endPtr++;
            }
            // 更新最大会议室数量
            maxRooms = max(maxRooms, rooms);
        }
        
        return maxRooms;
    }
    
    // 方法二：优先队列（最小堆）
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        // 按开始时间排序
        sort(intervals.begin(), intervals.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] < b[0];
             });
        
        // 创建最小堆，用于存储会议的结束时间
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        // 处理第一个会议
        minHeap.push(intervals[0][1]);
        
        // 处理剩余会议
        for (int i = 1; i < intervals.size(); i++) {
            // 当前会议的开始时间大于等于最早结束的会议时间，可以复用会议室
            if (intervals[i][0] >= minHeap.top()) {
                minHeap.pop(); // 移除已结束的会议
            }
            
            // 添加当前会议的结束时间
            minHeap.push(intervals[i][1]);
        }
        
        // 堆中的元素数量即为所需的会议室数量
        return minHeap.size();
    }
};

执行结果

C# 实现

• 执行用时：104 ms
• 内存消耗：40.6 MB

Python 实现

• 执行用时：52 ms
• 内存消耗：17.8 MB

C++ 实现

• 执行用时：16 ms
• 内存消耗：13.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	104 ms	40.6 MB	优先队列实现较为简洁
Python	52 ms	17.8 MB	heapq库使用简单，代码可读性高
C++	16 ms	13.4 MB	性能最佳，内存占用最小

代码亮点

1. 🎯 提供了两种解法（扫描线和优先队列），适用于不同的场景和偏好
2. 💡 扫描线算法通过分离开始和结束事件，将问题转化为事件处理，思路巧妙
3. 🔍 优先队列解法中及时清理已结束的会议，确保队列中只保留必要的信息
4. 🎨 代码结构清晰，变量命名有意义，注释详细，便于理解算法流程

常见错误分析

1. 🚫 忘记处理空数组的特殊情况
2. 🚫 扫描线算法中错误地更新最大会议室数量
3. 🚫 优先队列方法中忘记弹出已结束的会议
4. 🚫 优先队列使用错误的比较函数，导致堆顶不是最早结束的会议

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
扫描线算法	O(n log n)	O(n)	思路清晰，容易理解	需要额外空间存储开始和结束时间
优先队列	O(n log n)	O(n)	实现简洁，直接模拟会议室分配过程	需要使用额外的数据结构
暴力解法	O(n²)	O(n)	思路最简单	效率低下，不适用于大规模数据

相关题目

• LeetCode 252. 会议室 - 简单
• LeetCode 56. 合并区间 - 中等
• LeetCode 1094. 拼车 - 中等