Interval List Intersections

Interval List Intersections is a favorite because both lists are already sorted. The interviewer wants to see if you can use that order. A beginner compares every pair. A strong candidate walks two pointers through the lists at the same time. That second habit is the real skill being tested.

🎯 The Problem

You get two sorted lists of intervals, and you must find where they overlap. Here are the rules.

• An interval is a small range, like [1, 5], which covers every point from 1 to 5.
• Both lists are sorted by start time.
• The intervals inside each list never overlap each other.
• Return a new list of the intersections, the shared part of two intervals.

An intersection is the piece both intervals cover.

Let us look at an example. The first list is [[0,2],[5,10],[13,23],[24,25]]. The second list is [[1,5],[8,12],[15,24],[25,26]]. The shared pieces form the answer below.

Input:
  A = [[0,2],[5,10],[13,23],[24,25]]
  B = [[1,5],[8,12],[15,24],[25,26]]
Output:
  [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Explanation: each output interval is the part both A and B cover.

Two intervals overlap when one starts before the other ends. The shared part starts at the larger of the two starts and ends at the smaller of the two ends. If that start is past that end, there is no overlap.

Here is the shape of the problem on a number line. See where A and B cover the same points.

🐢 Approach 1: Check Every Pair (Brute Force)

The idea in one line: compare each interval in the first list against each one in the second.

The idea:

• Take every interval from the first list.
• Compare it against every interval in the second list.
• For each pair, check the overlap. If real, record the shared part.

How it works:

• It ignores the sorting and just tries all pairs.
• It does give the right answer.

Why it is weak:

• You compare pairs that can never overlap, like an early interval against a late one.
• With two long lists the pair count grows fast. The time is O(n × m).
• It throws away the gift that both lists are sorted.

Here is the check-every-pair code:

def interval_intersection(first_list, second_list):
    answer = []
    for a_start, a_end in first_list:
        for b_start, b_end in second_list:
            start = max(a_start, b_start)
            end = min(a_end, b_end)
            if start <= end:
                answer.append([start, end])
    return sorted(answer)

⚡ Approach 2: Two Pointers (Best)

The idea in one line: walk both sorted lists together with one pointer each.

What pointers give us:

• A pointer is an index saying which interval we look at right now in each list.
• Both lists are sorted by start, so the two pointers always move forward.

How one step works:

• Start one pointer at the first interval of each list.
• Find the overlap. It starts at the larger of the two starts and ends at the smaller of the two ends.
• If the start is not past the end, the overlap is real. Add it to the answer.

The clever move:

• Advance only the pointer whose interval ends first.
• That interval is finished. It cannot overlap anything later in the other list.
• The interval that ends later might still overlap the next one. So keep it.

Why it is fast:

• Each step moves at least one pointer forward.
• So each interval is touched once. The time is O(n + m).

Here is a dry run of the two pointers on the first few intervals. Watch which pointer moves.

Steps to Solve

1. Start a pointer at the first interval of each list.
2. While both pointers are still inside their lists, look at the two current intervals.
3. Find the overlap start, which is the larger of the two starts.
4. Find the overlap end, which is the smaller of the two ends.
5. If the overlap start is not past the overlap end, add that shared interval to the answer.
6. Advance the pointer whose interval has the smaller end, because that interval is finished.
7. Stop when either pointer reaches the end of its list.

#include <stdio.h>

int maxInt(int a, int b) { return a > b ? a : b; }
int minInt(int a, int b) { return a < b ? a : b; }

void intervalIntersection(int A[][2], int na, int B[][2], int nb) {
    int i = 0, j = 0;                  // one pointer per list
    printf("[");
    int first = 1;
    while (i < na && j < nb) {
        int lo = maxInt(A[i][0], B[j][0]);  // larger of the two starts
        int hi = minInt(A[i][1], B[j][1]);  // smaller of the two ends
        if (lo <= hi) {                     // a real overlap exists
            if (!first) printf(", ");
            printf("[%d, %d]", lo, hi);
            first = 0;
        }
        if (A[i][1] < B[j][1]) i++;    // A ends first, move A
        else j++;                      // otherwise move B
    }
    printf("]\n");
}

int main(void) {
    int A[4][2] = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
    int B[4][2] = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
    intervalIntersection(A, 4, B, 4);
    return 0;
}

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> intervalIntersection(vector<vector<int>>& A,
                                          vector<vector<int>>& B) {
    vector<vector<int>> result;
    int i = 0, j = 0;                  // one pointer per list
    while (i < (int)A.size() && j < (int)B.size()) {
        int lo = max(A[i][0], B[j][0]);   // larger of the two starts
        int hi = min(A[i][1], B[j][1]);   // smaller of the two ends
        if (lo <= hi) result.push_back({lo, hi});  // real overlap
        if (A[i][1] < B[j][1]) i++;    // A ends first, move A
        else j++;                      // otherwise move B
    }
    return result;
}

int main() {
    vector<vector<int>> A = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
    vector<vector<int>> B = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
    vector<vector<int>> res = intervalIntersection(A, B);
    cout << "[";
    for (size_t k = 0; k < res.size(); k++) {
        cout << "[" << res[k][0] << ", " << res[k][1] << "]";
        if (k + 1 < res.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

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

import java.util.ArrayList;
import java.util.List;

public class IntervalIntersections {
    public static int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;                  // one pointer per list
        while (i < A.length && j < B.length) {
            int lo = Math.max(A[i][0], B[j][0]);  // larger of the two starts
            int hi = Math.min(A[i][1], B[j][1]);  // smaller of the two ends
            if (lo <= hi) result.add(new int[] { lo, hi });  // real overlap
            if (A[i][1] < B[j][1]) i++;    // A ends first, move A
            else j++;                      // otherwise move B
        }
        return result.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        int[][] A = {{0, 2}, {5, 10}, {13, 23}, {24, 25}};
        int[][] B = {{1, 5}, {8, 12}, {15, 24}, {25, 26}};
        int[][] res = intervalIntersection(A, B);
        StringBuilder sb = new StringBuilder("[");
        for (int k = 0; k < res.length; k++) {
            sb.append("[").append(res[k][0]).append(", ").append(res[k][1]).append("]");
            if (k + 1 < res.length) sb.append(", ");
        }
        sb.append("]");
        System.out.println(sb.toString());
    }
}

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

def interval_intersection(A, B):
    result = []
    i, j = 0, 0                          # one pointer per list

    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])       # larger of the two starts
        hi = min(A[i][1], B[j][1])       # smaller of the two ends
        if lo <= hi:                     # a real overlap exists
            result.append([lo, hi])
        if A[i][1] < B[j][1]:            # A ends first
            i += 1                       # so move pointer i
        else:                            # B ends first or ties
            j += 1                       # so move pointer j

    return result


A = [[0, 2], [5, 10], [13, 23], [24, 25]]
B = [[1, 5], [8, 12], [15, 24], [25, 26]]
print(interval_intersection(A, B))

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

function intervalIntersection(A, B) {
  const result = [];
  let i = 0;
  let j = 0; // one pointer per list

  while (i < A.length && j < B.length) {
    const lo = Math.max(A[i][0], B[j][0]); // larger of the two starts
    const hi = Math.min(A[i][1], B[j][1]); // smaller of the two ends
    if (lo <= hi) result.push([lo, hi]); // a real overlap exists
    if (A[i][1] < B[j][1]) i++; // A ends first, move i
    else j++; // otherwise move j
  }

  return result;
}

const A = [
  [0, 2],
  [5, 10],
  [13, 23],
  [24, 25],
];
const B = [
  [1, 5],
  [8, 12],
  [15, 24],
  [25, 26],
];
console.log(JSON.stringify(intervalIntersection(A, B)));

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

Let us read the Python version line by line, because the two-pointer dance is the heart of it.

We begin with result = [] to hold the overlaps. Then i, j = 0, 0 puts one pointer at the start of each list. Pointer i walks list A and pointer j walks list B.

The loop runs while i < len(A) and j < len(B). We keep going only while both pointers are still inside their lists. The moment one list is done, no more overlaps can happen.

Inside, lo = max(A[i][0], B[j][0]) finds the start of the overlap. The shared part cannot begin before either interval begins. So it begins at the later start. Then hi = min(A[i][1], B[j][1]) finds the end of the overlap. The shared part must end when the first interval ends. So it ends at the earlier end.

Next if lo <= hi. This is the overlap test. If lo is not past hi, there is a real shared piece, so we append [lo, hi] to the result. If lo is greater than hi, the intervals do not touch and we add nothing.

Then the pointer move. if A[i][1] < B[j][1]: i += 1. The interval in A ends first. It is finished and cannot overlap anything later in B. So we advance i. Otherwise we advance j. We always drop the interval that ends earlier. That is what keeps each interval touched only once and makes the whole thing fast.

⏱️ Time and Space Complexity

The brute force compares every pair, so its time grows as the two lists multiply. The two-pointer version moves at least one pointer forward each step. So it touches each interval once. That gives O(n + m) time, where n and m are the two list lengths. The only extra space is the output list itself.

🧩 Key Takeaways

• ✅ The overlap of two intervals starts at the larger start and ends at the smaller end.
• ✅ If that start is past that end, the intervals do not overlap at all.
• ✅ Because both lists are sorted, two pointers can walk them together instead of checking every pair.
• ✅ Always advance the pointer whose interval ends first, because it cannot overlap anything later.
• ✅ Each interval is touched once, so the total time is O(n + m).

🚀 What’s Next?

• Merge Intervals
• Insert Interval