AlgoMaster Logo

Interval List Intersections

mediumFrequencyUpdated September 21, 2026

Understanding the Problem

We have two lists of non-overlapping intervals, each sorted by start time. We need to find all the places where an interval from the first list overlaps with an interval from the second list, and return those overlapping segments.

One way to read it: each list is a person's calendar, where every interval is a busy block. The intersections are the time slots where both people are busy at the same time.

Two intervals [a, b] and [c, d] overlap if and only if a <= d and c <= b. When they overlap, the intersection is [max(a, c), min(b, d)]. Because both lists are sorted and internally non-overlapping, we can process them with two pointers, comparing one interval from each list at a time.

Key Constraints:

  • 0 <= firstList.length, secondList.length <= 1000 → A brute force O(m * n) scan tops out near 1,000,000 operations, so it passes. The sorted, non-overlapping structure lets us drop to O(m + n).
  • 0 <= starti < endi <= 10^9 → Endpoints can be as large as 10^9, so we cannot index an array by time. We work with the intervals directly. The values fit comfortably in a 32-bit signed integer, so no overflow handling is needed.
  • Both lists are sorted and pairwise disjoint → This lets a two-pointer scan move strictly forward and never look backward.

Approach 1: Brute Force (Check All Pairs)

Intuition

Compare every interval from the first list against every interval from the second list. For each pair, check whether they overlap, and if so, add the intersection to the result.

A pair [a, b] and [c, d] overlaps when max(a, c) <= min(b, d), and the overlap is then [max(a, c), min(b, d)].

The output comes out sorted without extra effort. Both input lists are already sorted by start time, so scanning the outer loop in order produces intersections in increasing order.

Algorithm

  1. Initialize an empty result list.
  2. For each interval [a, b] in firstList:
    • For each interval [c, d] in secondList:
      • Compute lo = max(a, c) and hi = min(b, d).
      • If lo <= hi, the intervals overlap. Add [lo, hi] to the result.
  3. Return the result.

Visualization and Code

Loading animation...

This approach ignores the sorted, non-overlapping structure of the input. The next approach uses it: two pointers walk through both lists at once, advancing whichever interval ends first to reach O(m + n).

Approach 2: Two Pointers (Optimal)

Intuition

Use two pointers, one per list, and walk through both at once. At each step, take the current interval A = [a, b] from the first list and B = [c, d] from the second list. They overlap when a <= d and c <= b, and the intersection is [max(a, c), min(b, d)].

After checking the pair, advance the pointer for whichever interval ends first. The interval that ends first cannot overlap with anything else in the other list, so it is safe to discard. The interval that ends later might still overlap with the next interval in the other list, so it stays.

This mirrors the merge step in merge sort. Each pointer only moves forward, every interval is compared at most once, and the total work is O(m + n).

Algorithm

  1. Initialize two pointers: i = 0 (for firstList) and j = 0 (for secondList).
  2. Initialize an empty result list.
  3. While i < firstList.length and j < secondList.length:
    • Let A = firstList[i] and B = secondList[j].
    • Compute lo = max(A[0], B[0]) and hi = min(A[1], B[1]).
    • If lo <= hi, the intervals overlap. Add [lo, hi] to the result.
    • Advance the pointer whose current interval ends first: if A[1] < B[1], increment i. Otherwise, increment j.
  4. Return the result.

Visualization and Code

Loading animation...