You are given a one-dimensional stretch of pavement represented by a closed interval [pavement_start, pavement_end].
You are also given an ordered list of raindrops, where each drop wets its own segment [drop_start, drop_end].
The raindrops fall sequentially, one after another, in the exact order provided in the list.
Return the 1-based index of the first drop that causes the union of all covered segments to fully contain the pavement.
If the pavement is never fully covered, return -1.
给你一段地面区间 [start, end]，还有一堆“雨滴”，每个雨滴会覆盖一个小区间。
雨滴是一个一个按顺序落下的。
问题是：
👉 第几个雨滴落下之后，所有雨滴覆盖的范围合起来，刚好把整段地面完全覆盖了？
如果一直到最后都没覆盖完整，就返回 -1。
面试官一上来没有任何提示，直接丢题。
候选人确认边界：
“区间是闭区间吗？会有负数吗？drop 可以超出 pavement 吗？”
面试官点头，说：
“Yes, drops can be outside, only intersection matters.”
这个信息很关键——
👉 不需要关心完全在外面的部分，只要能贡献覆盖就行。
候选人一开始想的是：
“我每来一个 drop，就把所有区间 merge 一次，然后看有没有覆盖整个 pavement。”
这其实是很多人第一反应。
问题在哪？
每次 merge 全部区间，复杂度会炸（O(n²)级别）
面试官这里没有打断，只是问了一句：
“Can we do better than re-merging everything every time?”
候选人停了一下，开始换思路：
其实我们根本不需要维护所有区间
我们只需要知道：当前已经连续覆盖到哪里了
于是思路变成：
- 初始化一个当前覆盖区间
[cur_start, cur_end] - 每来一个 drop：
- 如果它能“接上”当前覆盖（有交集或能延伸）
- 就更新
cur_end
- 一旦
cur_start <= pavement_start且cur_end >= pavement_end
直接返回当前 index
面试官这里问了一个很关键的问题：
“What if drops come in a bad order?”
比如：
pavement: [0, 100]drops:
[50, 60]
[0, 10]
[10, 50]
如果你只按顺序“贪心延伸”，会出问题。
候选人这里卡了一下，然后意识到：
顺序是固定的，不能排序！
所以必须做到：
在“当前已有覆盖 + 新drop”之间做判断
而不是依赖全局排序
正确解法本质
这一题本质是在做：
动态区间合并 + 覆盖检测
但优化点在于：
不需要维护所有区间，只维护“当前有效覆盖范围”
关键判断只有两种：
1️⃣ 能接上当前覆盖
drop_start <= current_end
说明可以延伸
2️⃣ 完全没接上
那这个 drop 对当前覆盖没有贡献，可以忽略
🔥 面试中加的 follow-up
面试官继续加压：
👉 Follow-up 1
如果 drop 数量非常大（百万级），怎么办？
候选人回答：
👉 仍然是 O(n)，因为只扫一遍
👉 不做排序，不做全量 merge
👉 Follow-up 2
如果 drop 是乱序，可以排序吗？
候选人说：
👉 如果允许重排，那就变成经典：
👉 区间覆盖问题（interval covering）
复杂度可以做到：
O(n log n)
👉 Follow-up 3
如果是二维呢（雨滴变成矩形）？
候选人说：
👉 直接复杂度爆炸
👉 需要 sweep line + segment tree
面试官点头，这里基本就过了。
如果你最近有 VO 面试，提前准备这些 真实题型和思路，会非常关键。
我们也有代面试，面试辅助，OA代写等服务助您早日上岸~
