DSA Interval List Intersections

The problem

An interval is a stretch from a start to an end, written as a pair of numbers. Each input is a list of intervals. Inside one list the intervals are sorted and never overlap each other.

The answer lists every overlap between the two lists. An overlap is itself an interval. Two intervals that only touch at one point still count, and their overlap is that single point.

cases = [
    ([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]],
     [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]),
    ([[0, 2]], [[5, 9]], []),
    ([[1, 3]], [[3, 5]], [[3, 3]]),
]
for first, second, expected in cases:
    print("first", first)
    print("second", second)
    print("-> intersections:", expected)

The first case is the main one. It holds six overlaps, and two of them are single points. The third case is a touch and nothing more.

Intuition: an overlap runs from the later start to the earlier end

Two intervals overlap where both of them exist. That region cannot start before either interval starts. It cannot end after either interval ends.

So the overlap starts at the later of the two starts. It ends at the earlier of the two ends. When the later start passes the earlier end, the region is empty and there is no overlap.

a = [5, 10]
b = [8, 12]
start = max(a[0], b[0])
end = min(a[1], b[1])
print("later start:", start, "earlier end:", end, "overlap:", [start, end])
a = [0, 2]
b = [5, 9]
start = max(a[0], b[0])
end = min(a[1], b[1])
print("later start:", start, "earlier end:", end, "overlap exists:", start <= end)

The formula settles any single pair in one step. The problem is the pairing itself. Two lists offer many pairs, and most of them are nowhere near each other.

Brute force: every pair from both lists

The brute force pairs each interval of the first list with each interval of the second. It applies the formula to every pair. A counter records the pairs tested.

def brute(first, second):
    result = []
    pairs = 0
    for a in first:
        for b in second:
            pairs += 1
            start = max(a[0], b[0])
            end = min(a[1], b[1])
            if start <= end:
                result.append([start, end])
    return result, pairs

first = [[0, 2], [5, 10], [13, 23], [24, 25]]
second = [[1, 5], [8, 12], [15, 24], [25, 26]]
result, pairs = brute(first, second)
print("intersections:", result)
print("pair comparisons:", pairs)

Four intervals against four intervals make sixteen pairs. Only six of them overlap. The sorted order of the lists is what lets the sweep below skip the other ten pairs safely.

The optimal solution: advance the side that ends earlier

The state is one pointer into each list. The pair under the pointers is tested with the formula, and then the pointer whose interval ends earlier advances, because that interval can never meet anything further along the other list.

def intersect(first, second):
    i = j = 0
    moves = 0
    result = []
    while i < len(first) and j < len(second):
        start = max(first[i][0], second[j][0])
        end = min(first[i][1], second[j][1])
        if start <= end:
            result.append([start, end])
        moves += 1
        if first[i][1] < second[j][1]:
            i += 1
        else:
            j += 1
    return result, moves

cases = [
    ([[0, 2], [5, 10], [13, 23], [24, 25]], [[1, 5], [8, 12], [15, 24], [25, 26]],
     [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]),
    ([[0, 2]], [[5, 9]], []),
    ([[1, 3]], [[3, 5]], [[3, 3]]),
]
for first, second, expected in cases:
    result, moves = intersect(first, second)
    print("-> intersections:", result, "match:", result == expected, "comparisons:", moves)

The main case takes seven comparisons against the brute force's sixteen. Both lists are walked once, from front to back. Neither pointer ever moves backwards.

Walkthrough: two short lists swept together

The walk uses two intervals per side. Each comparison is printed with its overlap and its advance. Watch the pointer that moves each time.

first = [[0, 2], [5, 10]]
second = [[1, 5], [8, 12]]
i = j = 0
result = []
while i < len(first) and j < len(second):
    start = max(first[i][0], second[j][0])
    end = min(first[i][1], second[j][1])
    print("compare", first[i], "with", second[j])
    if start <= end:
        result.append([start, end])
        print(" overlap:", [start, end])
    if first[i][1] < second[j][1]:
        print(" first ends sooner; advance first")
        i += 1
    else:
        print(" second ends sooner; advance second")
        j += 1
print("intersections:", result)

Three comparisons produce three overlaps. The single point [5, 5] appears when the second list's first interval ends exactly where the first list's second interval begins. The touch counted, as the problem requires.

Complexity

The sweep advances one pointer per comparison, and each pointer moves at most the length of its list, so the time is O(m plus n) for lists of lengths m and n. The result list is the only extra space, and it holds the answer itself.

The brute force tests every pair, so its count is m times n. The counts below build alternating disjoint lists, where the sweep still walks both lists once.

def brute_pairs(first, second):
    pairs = 0
    for a in first:
        for b in second:
            pairs += 1
    return pairs

def sweep_moves(first, second):
    i = j = 0
    moves = 0
    while i < len(first) and j < len(second):
        moves += 1
        if first[i][1] < second[j][1]:
            i += 1
        else:
            j += 1
    return moves

for n in [4, 8, 16]:
    first = [[4 * k, 4 * k + 1] for k in range(n)]
    second = [[4 * k + 2, 4 * k + 3] for k in range(n)]
    print("intervals per list", n, "- brute pairs:", brute_pairs(first, second), " sweep comparisons:", sweep_moves(first, second))

At sixteen intervals per list the pair count is 256 against 31 sweep comparisons. The gap grows with the product of the lengths on one side and only their sum on the other.

Edge cases and pitfalls

An empty list on either side ends the sweep at once, and the answer is empty. One long interval can overlap many intervals on the other side, and the sweep records each one as the other pointer advances under it.

def intersect(first, second):
    i = j = 0
    moves = 0
    result = []
    while i < len(first) and j < len(second):
        start = max(first[i][0], second[j][0])
        end = min(first[i][1], second[j][1])
        if start <= end:
            result.append([start, end])
        moves += 1
        if first[i][1] < second[j][1]:
            i += 1
        else:
            j += 1
    return result, moves

print("empty first list:", intersect([], [[1, 2]])[0])
print("both empty:", intersect([], [])[0])
print("touching at a point:", intersect([[1, 3]], [[3, 5]])[0])
print("one interval over many:", intersect([[1, 10]], [[2, 3], [5, 6]])[0])
print("fully disjoint:", intersect([[1, 2]], [[4, 5]])[0])

The pitfall is the comparison that ends the overlap test. Using a strict less-than there would drop every single-point overlap. The test must allow the later start to equal the earlier end.