会议室
intervals=[[0,30],[5,10],[15,20]] 能否参加全部？
intervals=[[0,30],[5,10],[15,20]] 能否参加全部？
当前区间与已确认边界是重叠、相离还是需要更新？
按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
先说结论：这道题到底解决什么
怎样从“intervals=[[0,30],[5,10],[15,20]] 能否参加全部？”推导出 区间 · 排序 + 相邻判定，并证明每次状态变化都不会漏掉答案？
中心结论：按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
- 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
- 2.当前区间与已确认边界是重叠、相离还是需要更新？
- 3.不变量“排序后冲突只发生在相邻区间之间:若 i、j(i<j) 冲突,则 i..j 必连成重叠链。”为什么能保证算法安全前进？
完整题目与题意拆解
intervals=[[0,30],[5,10],[15,20]] 能否参加全部？
在本站主例中，intervals=[[0,30],[5,10],[15,20]] 能否参加全部？
算法最终需要得到或观察：排序后 [5,10].start < [0,30].end → 冲突,返回 false。
- • 输入：intervals=[[0,30],[5,10],[15,20]] 能否参加全部？
- • 机器需要维护：排序后 intervals、prev.end、扫描下标 i。
- • 最终可观察结果：排序后 [5,10].start < [0,30].end → 冲突,返回 false。
先看清算法到底要维护什么
先建立输入、目标、输出和第一批状态，不急着进入模板。
会议室问题:同一时刻需要的房间数 = 最大重叠数
第一层方案：暴力做法
两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。
暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。
重复工作究竟发生在哪里
把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。
会议室问题:同一时刻需要的房间数 = 最大重叠数
整体地图：先做什么，再做什么
- 1建模把输入翻译成“区间时间轴”，明确答案需要观察什么。
- 2状态只维护 排序后 intervals、prev.end、扫描下标 i。
- 3转移每一步按照 按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
- 4收尾读取 排序后 [5,10].start < [0,30].end → 冲突,返回 false。，并复核边界与复杂度。
区间时间轴：核心概念
排序把二维的任意关系压缩成从左到右的一次扫描。
这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：排序后 intervals、prev.end、扫描下标 i。
- • 排序后冲突只发生在相邻区间之间:若 i、j(i<j) 冲突,则 i..j 必连成重叠链。
建立“区间时间轴”心智模型
用主例建立核心状态，先预测下一步，再公开正确分支和理由。
会议室问题:同一时刻需要的房间数 = 最大重叠数
核心机制：状态如何一步步变化
按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
执行过程中持续维护：排序后 intervals、prev.end、扫描下标 i。
正确性依赖以下不变量：排序后冲突只发生在相邻区间之间:若 i、j(i<j) 冲突,则 i..j 必连成重叠链。
面试时可以压缩为：排序 O(n log n) 后从第 2 场起每场只和上一场比:cur.start < prev.end 立即返回 false;全部通过返回 true。线性扫描 O(n),空间 O(1)。
落到当前题，执行机制可以压缩为：按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。
一次状态转移为什么成立
集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。
在 0 需要新开一间,当前并发 1 间
正确性证明：为什么不会漏答案
初始化：算法开始时，全部合法候选仍在状态表示范围内；排序后冲突只发生在相邻区间之间:若 i、j(i<j) 冲突,则 i..j 必连成重叠链。
保持：执行“按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。”时，只删除已经能证明不可能的候选，并把新信息写回 排序后 intervals、prev.end、扫描下标 i。
终止：没有待处理状态或达到命中条件时，当前可观察结果就是“排序后 [5,10].start < [0,30].end → 冲突,返回 false。”。
完整执行过程
- 1题目与输入intervals=[[0,30],[5,10],[15,20]] 能否参加全部？ 因为：按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
- 2拆成起点流与终点流按时间顺序处理「会议开始」和「会议结束」。 因为：扫描线:起点 +1 房间,终点 -1 房间。
- 3时刻 0 有会议开始一个会议开始,占用一间。 因为：并发数即同一时刻重叠的区间数。
- 4时刻 5 有会议开始一个会议开始,占用一间。 因为：并发数即同一时刻重叠的区间数。
- 5时刻 10 有会议结束会议结束,释放一间。 因为：结束时刻不占用新房间(先结束再开始可复用)。
- 6时刻 15 有会议开始一个会议开始,占用一间。 因为：并发数即同一时刻重叠的区间数。
- 7至少需要 2 间扫描结束,峰值即答案。 因为：O(n log n) 排序 + O(n) 扫描。
- 8收尾与复杂度排序后 [5,10].start < [0,30].end → 冲突,返回 false。 因为：时间 O(n log n) · 空间 O(1)。按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
从输入完整走到可观察结果
从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。
会议室问题:同一时刻需要的房间数 = 最大重叠数
把动画和 Go 代码逐行对应
代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。
让每个动作都落到 Go 分支
重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。
会议室问题:同一时刻需要的房间数 = 最大重叠数
完整 Go 提交代码与最小测试
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
}func main() {
// 1. 主例
// 输入：mode="meeting-rooms", intervals=[[0,30],[5,10],[15,20]]
// 期望：排序后 [5,10].start < [0,30].end → 冲突,返回 false。
//
// 2. 失败 / 未命中
// 检查：用 <= 而非 < 会把边界相接(上一场结束=下一场开始)误判为冲突。
//
// 3. 边界
// 空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
//
// 4. 迁移
// LC56 合并区间；LC253 会议室 II；LC435 无重叠区间
}正确性与复杂度
执行过程中只保留仍可能影响答案的状态。按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
额外状态主要用于维护：排序后 intervals、prev.end、扫描下标 i。
- • 排序后冲突只发生在相邻区间之间:若 i、j(i<j) 冲突,则 i..j 必连成重叠链。
最容易写错的地方
用 <= 而非 < 会把边界相接(上一场结束=下一场开始)误判为冲突。
不排序就相邻比较:相邻不冲突不代表全局不冲突,必须先排序。
把本题当成 LC253 求最大房间数:这是判定 0/1 题,简单得多。
必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。
最后复盘：带走逻辑链
- 1题意intervals=[[0,30],[5,10],[15,20]] 能否参加全部？
- 2重复两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。
- 3优化按 start 排序后,只比较相邻区间:任意相邻 cur.start<prev.end 即冲突。
- 4证明排序后冲突只发生在相邻区间之间:若 i、j(i<j) 冲突,则 i..j 必连成重叠链。
- 5复杂度时间 O(n log n)，空间 O(1)
- • LC56 合并区间
- • LC253 会议室 II
- • LC435 无重叠区间