Merge overlapping corrections
Quick Overview
This question evaluates a candidate's ability to manage and manipulate overlapping intervals with multi-criteria tie-breaking, preserve original metadata across splits, and design efficient data structures and algorithms for producing non-overlapping correction spans.
Implement correctionMerge(corrections).
You are given a list of text-correction spans. Each correction applies to an inclusive interval [start, end] and has the following fields:
-
start: int— inclusive start index -
end: int— inclusive end index -
priority: int— higher value means higher priority -
change: enum— the modification to apply, such asDELETE,DEDUP,UPDATE,UPPERCASE, orLOWERCASE
Return a list of corrections such that no two output corrections overlap.
When two corrections overlap, resolve the overlap using these rules for every covered position:
-
The correction with the higher
prioritywins. -
If priorities are equal, the correction with the
smaller original span length
(end - start)wins. - If both are still equal, preserve the earlier correction in the input order.
If a correction loses only part of its interval, split it into the remaining non-overlapping pieces.
Important detail: if an interval is split, every fragment must keep the metadata of the original correction for future comparisons, including its original priority, input order, and original span length. In other words, after splitting (1,10,1,UPPERCASE) into (1,2,...) and (7,10,...), later tie-breaking must still treat both fragments as coming from the original span (1,10), not from shorter spans (1,2) or (7,10).
Example:
-
input:
(1,10,1,UPPERCASE),(3,6,1,LOWERCASE) -
output:
(1,2,1,UPPERCASE),(3,6,1,LOWERCASE),(7,10,1,UPPERCASE)
Assume the number of corrections can be large, so iterating over every character position is not allowed. Return the minimal sorted list of non-overlapping output segments.