Google VO 面试真题解析：重叠文本标注分段输出

Given a web page, we want to annotate text segments that may overlap.

(One example is Google Docs, where you can highlight some text and add a comment.)

We need to get a sequential list of annotation sets split at each boundary where the set of annotations changes.

Example:

Here’s a text with three annotations (X, Y, Z). Notice how the annotated text segments overlap (e.g. X annotates the segment some and Z annotates the segment e t).

Input: a text being annotated, and a list of intervals with annotation.

"some text"

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

Output: a sequential list of text chunks with its annotations.

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

这道题要求把一段文本上的多个标注区间按边界切分成若干连续片段，并输出每个片段对应的当前标注集合。核心思路是把所有区间起点和终点都当作扫描线事件，按位置排序后维护一个活动标注集合；当集合发生变化时，就把前一个位置到当前边界之间的文本片段记录下来。这样可以自然处理重叠区间，例如同一段文字同时被 X 和 Z 标注时，输出中会拆成更细的区间。