Interval List Intersections

Explanation & Solution

Description

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [startᵢ, endᵢ] and secondList[j] = [startⱼ, endⱼ]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that is either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Explanation: The intersections are computed pairwise between overlapping intervals from both lists.

Constraints

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= startᵢ < endᵢ <= 10⁹ (except single-point intervals where startᵢ == endᵢ)
0 <= startⱼ < endⱼ <= 10⁹ (except single-point intervals where startⱼ == endⱼ)
Each list is pairwise disjoint and sorted by start time

Approach

Intervals pattern

1. Initialize Two Pointers

Set i = 0 to point at the first interval in firstList
Set j = 0 to point at the first interval in secondList
Create an empty result array to collect intersections

2. Compare the Current Pair of Intervals

At each step we look at firstList[i] and secondList[j]
Compute the potential overlap:
lo = max(firstList[i][0], secondList[j][0]) — the later of the two start times
hi = min(firstList[i][1], secondList[j][1]) — the earlier of the two end times

3. Check If an Intersection Exists

If lo <= hi, the two intervals overlap and their intersection is [lo, hi]
Push [lo, hi] into the result array
If lo > hi, the intervals do not overlap — no intersection is added

4. Advance the Pointer With the Smaller End

If firstList[i][1] < secondList[j][1], increment i
The interval in firstList ends sooner, so it cannot overlap with any future interval in secondList
Otherwise, increment j
The interval in secondList ends sooner (or at the same time)
This greedy choice ensures we never miss an intersection

5. Loop Until One List Is Exhausted

Once either i or j goes out of bounds, there can be no more intersections
Return the result array

Key Insight

The intersection of [a, b] and [c, d] exists precisely when max(a, c) <= min(b, d), and equals [max(a, c), min(b, d)]
Because both lists are sorted and disjoint, advancing the pointer whose interval ends first is always correct — that interval cannot intersect any later interval in the other list

Time

O(m + n)each pointer advances at most m or n times respectively

Space

O(min(m, n)) — the result contains at most min(m, n) intersection intervals

Visualization

Input:

Interval Timeline[[0,2], [5,10], [13,23], [24,25]]

—

Press play to start visualization

CurrentCompareOverlapMerged

9 steps

Solution Code

Insert Interval

Non-overlapping Intervals