Intervals Example: Intersecting Two Sorted Lists of Intervals

Two pointers walk the lists together: the overlap of the current pair is from the later start to the earlier end, and the one that ends first moves on.

Intersecting two sorted lists of intervals walks one pointer through each list and takes the overlap of the current pair at every step. Each list is sorted by start and has no overlaps within it, like two people's free times in a day. The first list holds [1, 5], [8, 12] and [15, 20]; the second holds [3, 9] and [11, 16]. The question is when both are free.

Two closed intervals overlap from the later start to the earlier end, provided that start is at most that end. After comparing a pair, the interval that ends first moves on: it cannot overlap anything later in the other list, because every later interval there starts after the current one, which already reaches past it. Drawn on one axis, the overlaps are where both rows have a bar.

text

both lists on one axis
          0    5    10   15   20
first      =====  =====  ======
second       ======= ======
overlaps     ===  == ==  ==

The run walks the pairs in order, and the table records each comparison.

Each pair compared, its overlap, and which pointer moves
Pair compared	Overlap	Pointer moved
[1, 5] and [3, 9]	[3, 5]	First, since 5 ends before 9
[8, 12] and [3, 9]	[8, 9]	Second, since 9 ends before 12
[8, 12] and [11, 16]	[11, 12]	First, since 12 ends before 16
[15, 20] and [11, 16]	[15, 16]	Second, which runs out

The listing is the whole walk: the overlap on two lines, then the pointer whose interval ends first moves.

intersect.pypy

def intersect(first: list[list[int]], second: list[list[int]]) -> list[list[int]]:
    i = j = 0
    overlaps: list[list[int]] = []
    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:
            overlaps.append([start, end])
        if first[i][1] < second[j][1]:
            i += 1
        else:
            j += 1
    return overlaps


first = [[1, 5], [8, 12], [15, 20]]
second = [[3, 9], [11, 16]]
print("overlaps:", intersect(first, second))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

overlaps: [[3, 5], [8, 9], [11, 12], [15, 16]]

Every step moves one pointer, so the walk takes at most n + m steps for lists of n and m intervals: O(n + m) time, with no sort, because both lists arrive sorted. The interval that is not moved can overlap several in the other list, as [8, 12] does here. Returning the second list's [3, 9] whole is the common slip; the overlap is clipped at both ends.

← → move through sections and cards