LeetCode 252. 会议室
题目描述
✅ 252. 会议室
题意分析
判断一个人能否完整参加所有会议，也就是任意两场会议都不能在时间上重叠。一场结束的时刻等于另一场开始的时刻时，可以立即衔接。没有会议或只有一场会议时，答案都是
true。
解法：按开始时间排序后检查相邻区间
核心思路
[!blue]
先按开始时间升序排序，让会议的数组顺序与参加顺序一致。当前会议若早于前一场结束就开始，两场必然冲突，立即返回
false；否则这两场可以衔接。只检查前一场就够，是因为扫描到当前会议时，此前所有相邻会议都已通过检查，已经构成一条互不重叠的时间线。沿着这条时间线，结束时间也依次递增，所以前一场就是已处理会议中结束最晚的一场。当前开始时间只要不早于它的结束时间，就不会与更早的任何会议冲突。
从第一场开始逐一接入会议，每次检查通过都保持“已处理会议互不冲突”。若扫描结束，这个结论便覆盖所有会议；发现冲突时则已有两场无法同时参加，无需继续扫描。代码会原地改变输入区间的排列顺序。
解题步骤
- 按
intervals[i][0]，也就是开始时间升序排序。- 从第二场会议开始，将当前开始时间与前一场结束时间比较。
- 若
intervals[i][0] < intervals[i - 1][1]，返回false；相等时继续扫描。- 扫描结束返回
true。空数组和单元素数组不会进入循环，自然得到正确答案。
代码实现
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
for (int i = 1; i < intervals.length; i++) {
// 下一场开始时刻严格小于上一场结束时刻才冲突；两者相等时可以衔接。
if (intervals[i][0] < intervals[i - 1][1]) {
return false;
}
}
return true;
}
}
import "sort"
func canAttendMeetings(intervals [][]int) bool {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
for i := 1; i < len(intervals); i++ {
// 下一场开始时刻严格小于上一场结束时刻才冲突；两者相等时可以衔接。
if intervals[i][0] < intervals[i-1][1] {
return false
}
}
return true
}
复杂度分析
- 时间复杂度：$O(n \log n)$。排序占主导，之后只需 $O(n)$ 扫描。
- 空间复杂度：取决于排序实现；Java 对对象数组排序最坏使用 $O(n)$ 辅助空间，Go 排序栈为 $O(\log n)$。排序后的检查只使用常数个变量。
关键点总结
[!green]
- 排序确定时间顺序；检查过的前缀始终是一组互不重叠的会议。
- 在此前均无冲突的前提下，前一场就是结束最晚的已处理会议，无需额外维护最大结束时间。
- 两场首尾相接允许参加，重叠条件必须是严格小于。
- 本题只判断能否全部参加，发现一处冲突即可返回。
易错点总结
[!yellow]
- 冲突条件写成
<=，会把首尾相接的会议误判为重叠。- 比较的是当前开始时间与前一结束时间，不能只比较两个开始时间或两个结束时间。
- 未排序就检查相邻会议，会漏掉输入中不相邻但时间重叠的区间。
- Java 比较器直接相减可能溢出，使用
Integer.compare可以按开始时间正确排序。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 253. 会议室 II | 中等 | 本题只判断有无重叠，原题统计最多同时重叠会议数以确定房间数量。 |
| 435. 无重叠区间 | 中等 | 本题要求全部会议互不冲突，原题允许删掉最少区间再满足这一条件。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！