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],
}This problem asks you to split a text into consecutive chunks so that each chunk has a stable set of active annotations. A standard sweep-line approach works well: collect every interval start and end as events, sort the boundaries, and maintain the current active annotation set while moving from left to right. Whenever the active set changes, emit the segment between the previous boundary and the current one. This cleanly handles overlaps and produces the minimal partition of the annotated text.
