Waymo 的面试题经常有一种很典型的风格：题面看起来不复杂，但如果你一开始顺着直觉走，很容易掉进一个“局部看起来对、全局其实不稳”的坑里。
这道题就是这种类型。
如果把它改成更贴近自动驾驶场景的说法，可以这样理解：
系统正在监控一段目标道路，范围是一个闭区间 [roadStart, roadEnd]。
同时会按时间顺序接收到一批“路段观测片段”，每个片段也是一个闭区间 [segmentStart, segmentEnd]。
这些观测片段会一个一个到来，顺序固定，不能重排。
问题是：
第几个片段到来之后，这些已到达片段在目标道路上的联合覆盖，第一次把整段目标路完全盖住？
如果直到最后都没能完整覆盖，就返回 -1。
这题最容易让人误判的地方
很多人第一反应会是：
- 每来一个新区间
- 就把当前所有区间重新 merge 一遍
- 然后检查能不能覆盖目标区间
这个方向当然能做，但一旦区间数量大起来，重复全量 merge 的复杂度会非常难看。
所以面试里很容易马上被追问一句：
能不能比“每次把所有区间重合并一次”做得更好？
而这里最关键的一点，其实不是区间 merge 本身，而是：
输入顺序固定，不能排序。
这一点会直接杀死很多“我先排个序再扫一遍”的自然想法。
先别急着写代码，这题最值得先确认的边界
这道题特别适合先做几句 clarify，因为这些细节会直接影响后面的合并规则。
比较关键的点通常包括：
- 区间是不是闭区间
- 坐标会不会有负数
- 单个片段能不能完全落在目标道路之外
而这题里最关键的信息通常是：
片段可以超出目标道路，真正有意义的只有它和目标道路的交集。
也就是说，你不需要关心区间在目标区间外面那一部分。
每次真正参与覆盖判断的，只是它对 [roadStart, roadEnd] 的有效贡献。
这个点一旦想清楚，后面的状态空间会小很多。
为什么“维护当前能延伸到哪里”这个贪心不够稳
有些候选人会想到一种更轻量的做法：
- 维护一个当前已经连续覆盖到的位置
- 如果新片段能接上，就往右延
- 一旦覆盖到终点，就返回
这个想法在很多顺序漂亮的测试里会过，但它有一个根本问题：
它隐含假设了对你有帮助的区间会按“可延伸”的顺序到来。
可现实里输入顺序是固定但可能很乱。
例如：
- 目标区间是
[0, 100] - 到来的片段依次是
[50, 60]、[0, 10]、[10, 50]
如果你只盯着“当前连续覆盖能不能往右推”，第一个区间看起来没法从左端接上，第二个只能到 10，直到第三个才突然闭合。
这说明什么？
说明你不能只维护一个“当前最远右边界”，因为：
- 有些早到的片段虽然当下接不上
- 但它们会在未来和后来的片段拼起来
- 最终共同组成完整覆盖
所以这题不能被简化成单一右边界贪心。
正确建模：维护“当前已经形成的若干段不相交覆盖区间”
更稳的思路是把问题看成一个在线版的动态区间合并。
每来一个新区间，只做两件事：
- 先把它裁剪到目标道路内部
- 再把它和当前已经维护的覆盖区间集合合并
这里维护的不是所有历史原始区间，而是：
当前在目标道路上已经形成的、不相交的覆盖区间集合
这样做的好处是：
- 你不会丢掉那些“现在还接不到左端、但未来可能拼起来”的片段
- 你也不需要每次重新 merge 全部原始输入
你真正维护的是“合并后的状态”，而不是“原始历史”。
为什么要先裁剪到目标区间
这一步经常被很多人带过去，但其实很值得主动讲出来。
如果一个新片段是：
- 完全在目标区间外
- 或者只部分和目标区间相交
那么它真正对答案有用的，只有和目标区间的交集。
所以每次新区间到来时，可以先做：
- 左边界取
max(segmentStart, roadStart) - 右边界取
min(segmentEnd, roadEnd)
如果裁完之后左边大于右边，那说明这个片段对目标道路没有任何贡献，可以直接忽略。
这一层处理能让后面所有逻辑都只围绕目标区间内部展开，表达会清晰很多。
动态区间合并的核心思路
假设当前已经维护了一组按起点排序、彼此不重叠的覆盖区间。
当一个新的有效片段进来时，你需要做的是：
- 找到它左边可能和它相交或相接的区间
- 继续向右吸收所有与它重叠或接触的区间
- 合并成一个更大的新区间
- 再把这个新区间放回结构里
因为区间是闭区间，所以像：
[0, 10][10, 20]
这种在端点处相接的情况，也应该视为已经连通，不需要再拆开。
所以合并条件不是“严格重叠”，而是“重叠或接触”。
这也是这题比普通离线 merge intervals 更像工程题的地方：你需要在线地维护合并后的状态。
什么时候可以返回答案
这题问的是：
第几个片段出现后，目标区间第一次被完整覆盖。
所以在每次插入并完成合并后，只需要检查：
- 是否存在一个覆盖区间，它的左端点已经小于等于
roadStart - 并且它的右端点已经大于等于
roadEnd
一旦成立，就说明目标区间第一次被完整盖住，当前片段编号就是答案。
这里不需要再去算“总覆盖长度”。
因为总长度就算刚好够，也可能中间还有缝。
真正可靠的判断是：是否已经形成了一个能完整跨过目标区间的连续合并段。
这题为什么比“每次全量 merge”更优
如果你每来一个新区间都对所有历史区间重新排序并 merge，代价会非常高。
而如果你维护的是：
- 已经合并好的不相交区间集合
那么每次新区间到来时，真正需要处理的只是：
- 和它局部相邻的那几段
这使得整体复杂度更可控，也更符合 online processing 的语义。
一个比较自然的实现载体通常是：
- 有序映射
- 平衡树
- 或任何支持按起点查找相邻区间的数据结构
面试里不一定非要写出最重的工程实现，但一定要把这个状态维护思路说清楚。
面试里可能继续追问的几个方向
Follow-up 1：如果输入规模到百万级怎么办？
这类问题通常在问：
- 你现在是不是还在做全量重算
如果你已经切到了“维护合并后区间集合”的思路，这时就可以很自然地回答：
- 仍然是在线处理
- 不做全量重 merge
- 每个新区间只和局部相邻覆盖段发生关系
Follow-up 2：如果允许重排所有片段呢？
这时问题会立刻退化成经典的区间覆盖问题。
一旦允许排序，就可以：
- 先按起点排序
- 再用标准贪心检查是否能从左到右完整覆盖目标区间
复杂度自然会走向 O(n log n)。
Follow-up 3：如果从一维变成二维呢？
这也是非常典型的压轴追问。
一旦覆盖对象从线段变成矩形，问题就不再是简单区间合并了，复杂度会明显上升。
这时候一个比较合理的延伸方向通常是：
- sweep line
- segment tree
也就是把二维覆盖问题拆成一维扫描 + 动态维护。
不需要真的把二维完整写出来，但要体现你知道为什么一维思路不能直接原封不动搬过去。
这题在 Waymo 面试里真正考察的是什么
这题表面是区间题，但它更像是在看你有没有在线维护状态的能力。
真正的考点不是：
- 你会不会 merge intervals
而是：
- 你能不能意识到顺序固定，不能排序
- 你能不能避免每次全量重算
- 你能不能把问题抽象成“维护合并后的有效状态”
这也是 Waymo 这类题很常见的特点：
- 背景看起来业务化
- 第一眼直觉很容易错
- 真正正解通常来自更稳的状态维护
所以这题并不是在比谁刷题多，而是在比谁更快意识到“这不是静态区间题，而是在线覆盖问题”。
📌 最后总结
这道题最值得记住的，不是“第几个片段把地面盖住”这种表层叙述，而是它背后的结构：
- 输入顺序固定
- 不能排序
- 但又要动态判断是否已形成完整覆盖
一旦抓住这一点，最稳的解法就不是单一右边界贪心，而是：
- 每次先裁剪新区间到目标区间
- 再动态合并到当前覆盖区间集合中
- 最后判断是否已经形成完整跨越目标区间的一段
如果你最近在准备 Waymo 或类似风格的 VO，这类“在线维护区间状态”的题非常值得专门练。因为它特别容易暴露一个人到底是在套模板，还是在真正理解问题结构。
🚀 oavoservice：你的 Waymo VO 稳定输出保障
如果你最近有 Waymo、Google、Apple、LinkedIn、Amazon 这类 VO 面试，提前准备这种真实题型和 follow-up 思路会非常关键。
我们提供：
✅ 大厂 VO 实时辅助 — Coding、BQ、System Design 全程支持
✅ 真实题型 mock — 尽可能还原实际面试节奏
✅ 高压 follow-up 训练 — 不只练第一问，更练追问下的稳定输出
✅ 长题建模训练 — 帮你把业务背景快速翻译成可解的结构
如果你想提前感受最接近实战的反馈，也欢迎直接来聊。
👉 立即添加微信：Coding0201
Telegram: @OAVOProxy
Gmail: [email protected]