027. Intersect Two Interval Lists

Why this mechanism works

The overlap starts at the later start and ends at the earlier end. It exists only when start<end. After considering the two current intervals, the one ending first cannot intersect any later interval from the other list; that is the frontier that can be discarded safely.

State and boundaries

i and j are current interval indices. All intersections involving an interval before either frontier have been emitted.

Protocol

1. Compute max of starts and min of ends.
2. Emit if the resulting interval has positive length.
3. Advance the interval that ends first.
4. Stop when either source is exhausted.

Visualization

A: [0,2)   [5,10)
B:   [1,5)    [8,12)
=> [1,2), [8,10); no [5,5)

Python implementation

def intersect_intervals(a, b):
    i = j = 0
    output = []
    while i < len(a) and j < len(b):
        start = max(a[i][0], b[j][0])
        end = min(a[i][1], b[j][1])
        if start < end:
            output.append([start, end])
        if a[i][1] <= b[j][1]:
            i += 1
        else:
            j += 1
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 intersect_intervals: i = j = 0
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=0; j=0

L3 intersect_intervals: output = []
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=0; j=0; output=[]

L5 intersect_intervals: start = max(a[i][0], b[j][0])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=0; j=0; output=[]; start=1

L6 intersect_intervals: end = min(a[i][1], b[j][1])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=0; j=0; output=[]; start=1; end=2

L8 intersect_intervals: output.append([start, end])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=0; j=0; output=[[1, 2]]; start=1; end=2

L10 intersect_intervals: i += 1
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=1; j=0; output=[[1, 2]]; start=1; end=2

L5 intersect_intervals: start = max(a[i][0], b[j][0])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=1; j=0; output=[[1, 2]]; start=5; end=2

L6 intersect_intervals: end = min(a[i][1], b[j][1])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=1; j=0; output=[[1, 2]]; start=5; end=5

... 1 intermediate state changes omitted ...

L5 intersect_intervals: start = max(a[i][0], b[j][0])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=1; j=1; output=[[1, 2]]; start=8; end=5

L6 intersect_intervals: end = min(a[i][1], b[j][1])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=1; j=1; output=[[1, 2]]; start=8; end=10

L8 intersect_intervals: output.append([start, end])
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=1; j=1; output=[[1, 2], [8, 10]]; start=8; end=10

L10 intersect_intervals: i += 1
a=[[0, 2], [5, 10]]; b=[[1, 5], [8, 12]]; i=2; j=1; output=[[1, 2], [8, 10]]; start=8; end=10

L2 intersect_intervals: i = j = 0
a=[[1, 2]]; b=[[2, 3]]; i=0; j=0

L3 intersect_intervals: output = []
a=[[1, 2]]; b=[[2, 3]]; i=0; j=0; output=[]

L5 intersect_intervals: start = max(a[i][0], b[j][0])
a=[[1, 2]]; b=[[2, 3]]; i=0; j=0; output=[]; start=2

L6 intersect_intervals: end = min(a[i][1], b[j][1])
a=[[1, 2]]; b=[[2, 3]]; i=0; j=0; output=[]; start=2; end=2

L10 intersect_intervals: i += 1
a=[[1, 2]]; b=[[2, 3]]; i=1; j=0; output=[]; start=2; end=2

Why the solution is correct

The endpoint formula describes exactly the values shared by the current intervals. Disjoint sorted inputs ensure that the earlier-ending interval cannot overlap a later opposing interval after its current partner ends. Every possible positive-length overlap is therefore considered once.

Time and space

O(n+m) time and O(n+m) worst-case output storage; O(1) additional state.

Common mistakes

Using <= in the overlap test emits zero-length contacts. Advancing by the smaller start rather than the smaller end can discard an interval that still has future overlaps.

Reasoning card

Transfer exercise

Convert the solution to closed intervals and include singleton intersections such as [5,5].