这道 Google 面试题考的是一个很常见的文档编辑场景。

给你一段网页文本，用户可以对其中某些片段添加 annotation，比如高亮、评论、批注。问题是，这些 annotation 的范围可能互相重叠。现在需要把整段文本切成若干连续的小区间，每个小区间都要标出当前生效的 annotation 集合。

题目输入是一段文本和若干 annotation 区间：

text = "some text"

[0, 4) -> X
[5, 8) -> Y
[3, 6) -> Z

这里区间是左闭右开。
[0, 4) 表示覆盖下标 0、1、2、3，也就是 "some"。

把字符串下标标出来：

s o m e   t e x t
0 1 2 3 4 5 6 7

三个 annotation 分别是：

X 覆盖 [0, 4)
Y 覆盖 [5, 8)
Z 覆盖 [3, 6)

因为 Z 和 X 在 [3, 4) 重叠，Z 和 Y 在 [5, 6) 重叠，所以最终结果不能只按原来的三个区间返回，而是要在 annotation 状态发生变化的位置切开。

所有会发生变化的位置是：

0, 3, 4, 5, 6, 8

所以最终输出是：

[0, 3) -> [X]
[3, 4) -> [X, Z]
[4, 5) -> [Z]
[5, 6) -> [Y, Z]
[6, 8) -> [Y]

这道题的核心做法是 sweep line。

把每个 annotation 拆成两个事件：

start: 在 start 位置加入 annotation
end:   在 end 位置移除 annotation

例如：

[0, 4) -> X

可以拆成：

0: add X
4: remove X

所有事件放到一起以后，按位置从小到大扫描。扫描过程中维护一个当前生效的 annotation 集合。

每次来到一个新的边界点时，如果上一个位置到当前位置之间有内容，并且当前 annotation 集合不为空，就可以输出一段结果。

然后再处理当前位置的 add/remove 事件，更新当前集合，继续往后扫。

这题需要注意一个细节：同一个位置可能同时有 annotation 结束和开始。因为题目使用的是 [start, end)，所以 end 位置本身已经不属于旧 annotation。实现时可以在同一个坐标统一处理所有 remove 和 add，只要保证输出区间是在处理当前事件之前生成的，就不会错。

面试中可以这样解释思路：

先把所有 annotation 转换成边界事件。然后按坐标排序，从左到右扫描。扫描时维护一个 active set，表示当前有哪些 annotation 正在生效。每两个相邻边界之间，active set 不会变化，所以这一段就是一个稳定的 chunk。只要 active set 不为空，就把这个区间和对应的 annotation 集合加入答案。

时间复杂度是 O(n log n)，其中 n 是 annotation 数量。排序事件需要 O(n log n)，扫描过程是线性的。空间复杂度是 O(n)，用于保存事件和当前 active set。

这道题看起来像字符串题，本质上更像区间合并和扫描线。只要抓住“在 annotation 集合变化的位置切分”这个点，整体就很清楚。

csoahelp 做的就是这种场景里的实时辅助，题目刚读完就能给出完整思路，现场不用卡壳。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~