江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode第252题：会议室

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

题目描述

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入: intervals = [[0,30],[5,10],[15,20]]
输出: false
解释: 存在重叠，一个人在同一时间只能参加一个会议。

示例 2：

输入: intervals = [[7,10],[2,4]]
输出: true
解释: 一个人可以先参加 [2,4] 的会议，然后参加 [7,10] 的会议。

提示

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti < endi <= 10^6

解题思路

方法：排序 + 判断重叠

这个问题的核心是判断任意两个会议时间是否存在重叠。如果存在重叠，则一个人不能参加所有会议；如果不存在重叠，则可以参加所有会议。

关键点

  • 会议时间重叠的定义：一个会议的开始时间早于另一个会议的结束时间，且该会议的结束时间晚于另一个会议的开始时间
  • 可以通过排序简化问题，按照会议的开始时间排序
  • 排序后，只需要检查相邻会议是否重叠

具体步骤

  1. 按照会议的开始时间对所有会议进行排序
  2. 遍历排序后的会议时间，检查当前会议的开始时间是否小于前一个会议的结束时间：
    • 如果是，说明存在重叠，返回 false
    • 如果不是，继续检查下一个会议
  3. 如果遍历完所有会议都没有发现重叠，返回 true

复杂度分析

  • 时间复杂度：O(n log n)，其中 n 是会议的数量。排序需要 O(n log n) 的时间，遍历数组需要 O(n) 的时间。
  • 空间复杂度：O(1) 或 O(n)，取决于排序算法的实现。不考虑排序的额外空间，我们只需要常数级别的空间。

图解思路

排序前后对比表

会议编号 原始会议时间 排序后会议时间
1 [0, 30] [0, 30]
2 [5, 10] [5, 10]
3 [15, 20] [15, 20]

会议重叠检查表

当前会议 前一个会议 当前会议开始时间 前一个会议结束时间 是否重叠 结果
[5, 10] [0, 30] 5 30 是 (5 < 30) false
[15, 20] [5, 10] 15 10 否 (15 >= 10) 继续

代码实现

C# 实现

public class Solution {
    public bool CanAttendMeetings(int[][] intervals) {
        // 按照会议开始时间排序
        Array.Sort(intervals, (a, b) => a[0] - b[0]);
        
        // 检查相邻会议是否重叠
        for (int i = 1; i < intervals.Length; i++) {
            // 如果当前会议的开始时间小于前一个会议的结束时间，存在重叠
            if (intervals[i][0] < intervals[i-1][1]) {
                return false;
            }
        }
        
        return true;
    }
}

Python 实现

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # 按照会议开始时间排序
        intervals.sort(key=lambda x: x[0])
        
        # 检查相邻会议是否重叠
        for i in range(1, len(intervals)):
            # 如果当前会议的开始时间小于前一个会议的结束时间，存在重叠
            if intervals[i][0] < intervals[i-1][1]:
                return False
        
        return True

C++ 实现

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        // 按照会议开始时间排序
        sort(intervals.begin(), intervals.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[0] < b[0];
             });
        
        // 检查相邻会议是否重叠
        for (int i = 1; i < intervals.size(); i++) {
            // 如果当前会议的开始时间小于前一个会议的结束时间，存在重叠
            if (intervals[i][0] < intervals[i-1][1]) {
                return false;
            }
        }
        
        return true;
    }
};

执行结果

C# 实现

  • 执行用时：84 ms
  • 内存消耗：27.9 MB

Python 实现

  • 执行用时：36 ms
  • 内存消耗：16.9 MB

C++ 实现

  • 执行用时：12 ms
  • 内存消耗：11.7 MB

性能对比

语言 执行用时 内存消耗 特点
C# 84 ms 27.9 MB 代码简洁易读，性能适中
Python 36 ms 16.9 MB 语法最简洁，性能良好
C++ 12 ms 11.7 MB 性能最佳，内存占用最小

代码亮点

  1. 🎯 核心算法通过排序将问题简化，只需检查相邻会议是否重叠
  2. 💡 利用 Lambda 表达式简化排序操作，提高代码可读性
  3. 🔍 提前返回的策略，一旦发现重叠立即返回 false，不必检查所有会议
  4. 🎨 三种语言实现保持一致的算法思路，便于不同语言背景的读者理解

常见错误分析

  1. 🚫 忘记对会议时间进行排序，导致无法正确检测重叠
  2. 🚫 排序使用了错误的比较条件，如按结束时间而非开始时间排序
  3. 🚫 重叠判断条件错误，需要判断的是当前会议的开始时间与前一个会议的结束时间
  4. 🚫 遗漏空数组的特殊情况处理（当没有会议时应返回 true）

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
排序 + 相邻检查 O(n log n) O(1) 简单直观，易于实现 需要修改原数组或创建副本
暴力比较 O(n²) O(1) 无需排序，思路最简单 效率低下，不适用于大规模数据
扫描线算法 O(n log n) O(n) 可处理更复杂的区间问题 实现较复杂，本题不需要

相关题目