会议室安排问题

题目

会议室安排问题

信息

• 类型：问答
• 难度：⭐⭐

考点

贪心策略选择,区间排序,算法设计

快速回答

解决会议室安排问题的核心贪心策略：

1. 将会议按结束时间升序排序
2. 初始化计数器为1，记录当前会议结束时间
3. 遍历后续会议：
   • 若会议开始时间 ≥ 当前结束时间
   • 则选择该会议并更新结束时间

时间复杂度：O(n log n)，空间复杂度：O(1)

解析

问题描述

给定会议时间数组 intervals，每个元素 [start_i, end_i] 表示会议的开始和结束时间。计算在同一个会议室不冲突的情况下最多能安排的会议数量（当 end_i ≤ start_j 时视为不冲突）。

贪心原理

核心思想：每次选择结束时间最早的会议，为后续会议留下更多时间。证明：

1. 设最优解包含 k 个会议
2. 贪心选择的第一个会议结束时间 ≤ 任何其他选择的结束时间
3. 剩余问题转化为规模更小的子问题
4. 通过数学归纳法可证明全局最优

代码实现（Python）

def max_meetings(intervals):
    if not intervals:
        return 0

    # 按结束时间升序排序
    intervals.sort(key=lambda x: x[1])

    count = 1
    current_end = intervals[0][1]

    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start >= current_end:  # 检查时间冲突
            count += 1
            current_end = end

    return count

# 测试示例
intervals = [[1, 3], [2, 4], [3, 5], [4, 6]]
print(max_meetings(intervals))  # 输出: 3

最佳实践

• 排序优化：使用快速排序或归并排序保证 O(n log n) 时间复杂度
• 边界处理：空输入、单会议、全冲突等特殊情况
• 空间优化：原地排序避免额外空间

常见错误

• 按开始时间排序：反例 [[1,10], [2,3], [3,4]] 会错误选择第一个会议
• 忽略相等情况：未处理 end_i == start_j 的边界条件
• 双重循环：使用 O(n²) 暴力解法导致超时

扩展知识

• 变体问题：
  • 需要安排所有会议的最少会议室数（LeetCode 253）
  • 带权值的最大收益会议安排
• 算法对比：
  • 动态规划解法：O(n²) 时间复杂度
  • 贪心优势：高效解决区间调度类问题
• 实际应用：CPU 任务调度、铁路轨道安排、酒店房间预订