252. 会议室（简单）

Blind 75 › 252. 会议室（简单）（第 4 章）

题目

给定若干场会议，每场用 [开始时间, 结束时间) 表示；问：一个人能否一场不落地参加所有这些会议，且中间没有任何两场在时间上重叠。

换句话说：任意两场会议，都不能出现“上一场还没结束，下一场已经开始”的情况。

自造示例：[[0,3],[2,5],[5,7]] → false（第 1 场 [0,3] 与第 2 场 [2,5] 重叠）。

另一个自造示例：[[1,3],[3,6],[6,8]] → true（上一场 3 点结束、下一场 3 点开始，可以无缝衔接）。

约束：会议数 0 ~ 10⁴；每场恰有两个整数，0 ≤ 开始时间 < 结束时间 ≤ 10⁶。

一句话：先按开始时间排序，再检查“上一场结束 > 下一场开始”是否成立；只要有一处成立，就说明有冲突。

最直白的做法是两两比较：对任意两场会议，看前一场的结束是否晚于后一场的开始，或反过来。这样要检查 O(n²) 对；n = 10⁴ 时约 5×10⁷ 对，勉强但浪费，而且大量比较是重复的。

关键观察：题目问的是“能否都参加”，并没有规定会议必须按输入顺序开。既然可以自由安排顺序，就先按开始时间排序。排序之后有一个强结论：如果任意两场有冲突，那么一定存在相邻的两场也有冲突；反过来，相邻两场都不冲突，则所有会议都不冲突。

为什么只看相邻？设排好序后第 i 场和更靠后的第 k 场重叠，即 start_k < end_i。排序后 start_{i+1} ≤ start_k，于是 start_{i+1} < end_i，说明第 i 场已经和第

🔒

您已阅读试读部分，购买后即可解锁全文。

⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。