Overlap of Two Span Lists
Problem
Two people share their free time as lists of closed spans [start, end]. Each list is sorted by start, and the spans within one list never overlap. Return the spans when both are free, sorted by start. A span that shrinks to a single point, such as [5, 5], still counts.
Examples
Input: a = [[0, 2], [5, 10], [13, 23], [24, 25]], b = [[1, 5], [8, 12], [15, 24], [25, 26]]
Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]Input: a = [[1, 7]], b = [[3, 10]]
Output: [[3, 7]]
Why: the overlap starts at the later start and ends at the earlier endInput: a = [[1, 3], [5, 9]], b = []
Output: []
Why: edge case, one person is never freeHints
0 / 3
Take one span from each list. What is their overlap, and how can you tell that there is none?
Two spans overlap from the later of their starts to the earlier of their ends, and only if that start is not after that end. After comparing them, the span that ends first cannot overlap anything else in the other list.
Keep one pointer per list. Record the overlap of the two current spans if it is not empty, then advance the pointer whose span ends first. Stop when either list runs out.
Solution
Two closed spans overlap on [max of starts, min of ends] whenever that start is not after that end. Both lists are sorted and internally disjoint, so a two-pointer walk suffices: after comparing the current pair, the span that ends first has no future partner in the other list, since every later span there starts after the current one, and it can be dropped. The other span stays, because it may still overlap the next span of the first list. Each step drops one span, so time is O(m plus n) and space is O(1) beyond the output.
def overlaps(a, b):
out, i, j = [], 0, 0
while i < len(a) and j < len(b):
lo = max(a[i][0], b[j][0])
hi = min(a[i][1], b[j][1])
if lo <= hi:
out.append([lo, hi]) # they share [lo, hi]
if a[i][1] < b[j][1]:
i += 1 # a's span is finished
else:
j += 1
return out
print(overlaps([[0, 2], [5, 10], [13, 23]], [[1, 5], [8, 12], [15, 24]])) # -> [[1, 2], [5, 5], [8, 10], [15, 23]]
print(overlaps([[1, 7]], [[3, 10]])) # -> [[3, 7]]
print(overlaps([[1, 3], [5, 9]], [])) # -> []Stuck on the idea rather than the code? Merge Intervals covers it.