Interval List Intersections

The last problem in the section brings back two pointers. Two lists are already sorted, so no sort is needed — just two fingers walking forward, one per list, like merging two sorted arrays.

The problem

You are given two lists of closed intervals. Each list is sorted by start, and within each list no two intervals overlap. Return every intersection between an interval of the first list and an interval of the second list, in sorted order. A single shared point counts as an intersection.

• first = [[1, 4], [6, 9], [12, 15]], second = [[2, 7], [8, 13], [15, 18]] → [[2, 4], [6, 7], [8, 9], [12, 13], [15, 15]]. The last one is a single point: [12, 15] and [15, 18] share only 15.
• first = [[1, 3]], second = [] → [].

Constraints: 0 ≤ m, n ≤ 1000; intervals within a list are sorted and disjoint.

Clarifying questions

• Are endpoints included? Yes, the intervals are closed, so [3, 3] is a valid answer.
• Can one list be empty? Yes; then the answer is empty.
• Can an interval in one list overlap several in the other? Yes — [2, 7] above overlaps both [1, 4] and [6, 9].

Approach 1: every pair

The overlap of two closed intervals a and b is [max(a.start, b.start), min(a.end, b.end)], and it exists when that low end is not above the high end. Check every pair:

1def intersect_brute(first: list[list[int]], second: list[list[int]]) -> list[list[int]]:2    """Check every pair of intervals."""3    result = []4    for a in first:5        for b in second:6            low, high = max(a[0], b[0]), min(a[1], b[1])7            if low <= high:8                result.append([low, high])9    return sorted(result)

Where does [max of starts, min of ends] come from? A point is in both intervals when it is at or after both starts and at or before both ends. "At or after both starts" means at or after the larger start; "at or before both ends" means at or before the smaller end. If the larger start is past the smaller end, no point qualifies, and the intervals do not meet. That is the overlap test from the core lesson, read as a range.

Time O(m × n) for the pairs, plus a sort of the results. At 1,000 intervals each, that is a million checks — it passes, but it ignores that both lists are sorted. At 10⁵ each it would be 10¹⁰.

The key insight

Put one finger on each list, i on first and j on second. Compare the two current intervals, record their overlap if there is one, and then move the finger whose interval ends first.

Why is that safe? Say first[i] ends before second[j] does. Every later interval in second starts after second[j] ends — the list is disjoint and sorted — so it also starts after first[i] ends. So first[i] cannot meet anything else in second. It is finished, and you can move past it. The interval that ends later stays, because it may still reach the next interval of the other list, as [2, 7] does.

Each step moves one finger forward by one, so there are at most m + n steps.

Here are the two lists on one number line. Read it from left to right, and notice that the answer is simply every stretch where both rows are covered at once:

          1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18first     [===========]       [===========]           [===========]second        [===================]   [===================]       [===========]both          [=======]       [===]   [===]           [===]       *

The * at 15 is the single shared point.

Approach 2: two pointers

1def intersect(first: list[list[int]], second: list[list[int]]) -> list[list[int]]:2    """Two pointers; advance whichever interval ends first."""3    result: list[list[int]] = []4    i = j = 05    while i < len(first) and j < len(second):6        low = max(first[i][0], second[j][0])7        high = min(first[i][1], second[j][1])8        if low <= high:                          # closed: a single point counts9            result.append([low, high])10        if first[i][1] < second[j][1]:           # first[i] can meet nothing else11            i += 112        else:13            j += 114    return result

Dry run on first = [[1, 4], [6, 9], [12, 15]], second = [[2, 7], [8, 13], [15, 18]].

i has passed the end of first, so the loop stops. Result [[2, 4], [6, 7], [8, 9], [12, 13], [15, 15]]. Notice that [2, 7] stayed for two rows and [6, 9] for two rows: a long interval waits while the other finger walks.

Complexity. At most m + n iterations, each O(1): O(m + n) time. Space O(1) besides the output. The results come out sorted without any sort, because the fingers only move forward.

Edge cases

• One list empty: the loop never runs; the result is [].
• Touching across lists, [1, 3] and [3, 5]: low 3, high 3, so [3, 3] is recorded. With < instead of <=, single points would be lost.
• Equal ends, [1, 5] and [2, 5]: the else branch moves j. That is safe — the next interval in second starts after 5, so [1, 5] meets nothing more and is moved past on the next step.
• One interval covering the whole other list, [[0, 100]] against many small ones: j walks through all of them while i stays, and each small interval is its own intersection.

Follow-ups

• "Return the union instead of the intersection." Merge the two sorted lists by start (like merging sorted arrays), then run the Merge Intervals sweep: O(m + n).
• "Find the free time common to every employee" (Employee Free Time). Merge all schedules into one sorted list of busy intervals, then report the gaps between consecutive merged intervals. With k sorted schedules, a heap of one head per schedule does the merge in O(N log k).
• "Intersect k lists, not two." Intersect them pairwise, reusing this function: the running result can only shrink.