Cut a Span Out of Sorted Spans
Problem
A set of numbers is stored as a sorted list of disjoint half-open spans [a, b), each covering every number from a up to but not including b. Given one more span cut = [lo, hi), remove every number it covers from the set and return what is left, again as a sorted list of disjoint spans.
Examples
Input: spans = [[0, 2], [3, 4], [5, 7]], cut = [1, 6]
Output: [[0, 1], [6, 7]]
Why: the cut trims the first span, swallows the second and trims the thirdInput: spans = [[0, 5]], cut = [2, 3]
Output: [[0, 2], [3, 5]]
Why: a cut inside one span splits it into twoInput: spans = [[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], cut = [-1, 4]
Output: [[-5, -4], [-3, -2], [4, 5], [8, 9]]
Why: edge case, spans entirely outside the cut pass through untouchedHints
0 / 3
Look at each span on its own. Against the cut it can only be entirely before it, entirely after it, or overlapping it.
With half-open spans, [a, b) misses [lo, hi) exactly when b <= lo or a >= hi. Those spans are kept whole.
An overlapping span can leave up to two pieces: [a, lo) if it starts before the cut, and [hi, b) if it ends after it. Emit whichever of the two exist, in that order.
Solution
The list is already sorted and disjoint, so one pass in order is enough and the output stays sorted without any extra work. Each span is compared with the cut once: if they do not overlap it is copied, and if they do, only the parts sticking out on the left and on the right survive. A span that the cut covers completely produces neither part and disappears, and a span that the cut lands inside produces both, which is the split. Using half-open spans keeps the arithmetic clean, because the surviving pieces end exactly at lo and start exactly at hi with no plus or minus one. Time is O(n) and the output holds at most n + 1 spans.
def cut_span(spans, cut):
lo, hi = cut
out = []
for a, b in spans:
if b <= lo or a >= hi: # no overlap: keep the whole span
out.append([a, b])
continue
if a < lo:
out.append([a, lo]) # the part left of the cut survives
if b > hi:
out.append([hi, b]) # the part right of the cut survives
return out
print(cut_span([[0, 2], [3, 4], [5, 7]], [1, 6])) # -> [[0, 1], [6, 7]]
print(cut_span([[0, 5]], [2, 3])) # -> [[0, 2], [3, 5]]
print(cut_span([[-5, -4], [-3, -2], [1, 2], [3, 5], [8, 9]], [-1, 4])) # -> [[-5, -4], [-3, -2], [4, 5], [8, 9]]Stuck on the idea rather than the code? Insert Interval covers it.