← DSA Atlas
Dedicated problem page · #986

Interval List Intersections

MediumIntervals and Sweep LineTwo-pointer interval intersectionMerge two sorted interval lists by advancing the pointer with the smaller end
Solve on LeetCode ↗
986
MediumIntervals and Sweep LineMerge two sorted interval lists by advancing the pointer with the smaller endTwo-pointer interval intersection

Interval List Intersections

Given two lists of closed intervals, firstList and secondList, each sorted and internally pairwise-disjoint, return the intersection of the two lists: every interval covered by BOTH, in sorted order.

Open official problem prompt ↗
In plain English

Produce every time span that appears in both schedules, given two clean sorted timelines.

Picture it like this

Two people slide their finger down their own sorted list of busy blocks. At each moment they compare the block each finger points to; where the blocks overlap they note the shared window, then whoever's block finishes first moves their finger down.

Example
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]]
Why
Each output interval is the overlap of one interval from each list, e.g. [0,2] ∩ [1,5] = [1,2].
Constraints
0 <= firstList.length, secondList.length <= 1000firstList.length + secondList.length >= 10 <= start_i <= end_i <= 10^9Each list is sorted and pairwise disjoint
Pattern lesson

See the pattern, then code

Two-pointer interval intersection
Recognition clue

Two already-sorted interval lists whose pairwise overlaps are wanted is the textbook two-pointer merge; you never need nested loops.

↗
Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. For the current pair, the overlap is [max of starts, min of ends], which is real only when that low bound does not exceed the high bound. Then discard whichever interval ends first, because it cannot intersect anything further right.

New words, made simpleKnow these before the algorithm
Closed interval
[a, b] includes both endpoints, so [24,24] is a valid single-point interval
Intersection
The set of times contained in both intervals, itself an interval or empty
Two pointers
Independent indices advancing through two sorted sequences in linear time
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Brute-force all pairs

Ignores the sorted order and does redundant work.

Compare every interval of the first list against every interval of the second.

Time O(m * n)Space O(1)
Best choiceTwo-pointer sweep

Optimal linear merge that fully exploits the sorted, disjoint structure.

Walk both sorted lists together, intersecting the current pair and advancing the earlier-ending interval.

Time O(m + n)Space O(1)
The rule we keep true

Invariant

Every intersection lying entirely to the left of both current pointers has already been emitted, and no future interval can intersect an interval that has already been passed.

Why this is correct

Reasoning

Two closed intervals [a1,b1] and [a2,b2] overlap exactly when max(a1,a2) <= min(b1,b2). After handling the current pair, the interval with the smaller end can never overlap any interval further right in the other list (all of those start at or beyond the current position and this interval already ended), so advancing that pointer discards nothing useful and guarantees termination.

The algorithm in three movesSay these aloud before coding
1Point i and j at the fronts of the two lists

i=0,j=0: max(0,1)=1, min(2,5)=2 -> [1,2]

2Compute lo = max(starts), hi = min(ends) for the current pair

2 < 5 -> i++

3If lo <= hi, record [lo, hi]

i=1,j=0: max(5,1)=5,min(10,5)=5 -> [5,5]

4Advance the pointer whose interval has the smaller end, and repeat until one list is exhausted

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
[0,2]0
[1,5]1
[5,10]2
[8,12]3
1 · Read[0,2] & [1,5]
2 · Asklo<=hi?
3 · Update statelo=1, hi=2
4 · ResultEmit [1,2]; 2<5 so i++
Key takeaway

The overlap of [0,2] and [1,5] is [1,2]; then the interval ending sooner is advanced.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Set up

    Two pointers at the fronts and an empty result list.

  2. 2
    Lines 6-7Candidate overlap

    lo is the later start, hi the earlier end; together they bound the potential intersection.

  3. 3
    Lines 8-9Emit if valid

    A real overlap exists only when lo <= hi (inclusive, since intervals are closed).

  4. 4
    Lines 10-13Advance the smaller end

    The interval that ends first is done and cannot meet anything further right, so drop it.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Either list empty returns []
  • Intervals touching at one point like [5,10] and [1,5] intersect at [5,5]
  • One long interval overlapping many short ones in the other list
  • Fully disjoint lists return []
!

Common beginner mistakes

  • Using '<' instead of '<=' for lo vs hi and dropping single-point intersections like [5,5]
  • Advancing both pointers when ends are equal, which can skip a valid future overlap; advance only one
  • Comparing starts to decide which pointer to move instead of comparing ends
Check your understanding

When both current intervals end at the same coordinate, which pointer should advance and why?

More in Intervals and Sweep Line

#56Merge IntervalsSort by start, then sweep-and-merge#57Insert IntervalThree-phase interval splice#435Non-overlapping IntervalsGreedy: sort by end, keep earliest finisher#253Meeting Rooms IISweep line / min-heap of end times#228Summary RangesGroup consecutive runs#252Meeting RoomsSort by start, check adjacent overlap