3.31 Interval List Intersections

3.31.1 Problem Metadata

3.31.2 Description

Given two lc-lists of disjoint closed intervals sorted by start time, return their intersections.

3.31.3 Examples

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]]

3.31.4 Constraints

  • 0 <= len(A), len(B) <= 1000
  • Intervals are pairwise disjoint within each lc-list and sorted

3.31.5 Solution - Two Pointers

3.31.5.1 Walkthrough

Traverse both lc-lists with indices i and j. For each pair of intervals, compute the overlap as start = max(A[i].start, B[j].start) and end = min(A[i].end, B[j].end). If start <= end, append it. Advance the pointer whose interval ends first.

3.31.5.2 Analysis

  • Time Complexity: O(m + n)
  • Space Complexity: O(1) excluding output

3.31.5.3 Implementation Steps

  1. Initialize i = j = 0, result lc-list.
  2. While i < len(A) and j < len(B):
    1. start = max(A[i][0], B[j][0]), end = min(A[i][1], B[j][1]).
    2. If start <= end, append [start, end].
    3. Increment pointer whose interval ends first.
  3. Return the result lc-list as an array.

3.31.5.4 Code - Java

public int[][] intervalIntersection(int[][] A, int[][] B) {
    List<int[]> result = new ArrayList<>();
    int i = 0, j = 0;

    while (i < A.length && j < B.length) {
        int start = Math.max(A[i][0], B[j][0]);
        int end = Math.min(A[i][1], B[j][1]);

        if (start <= end) {
            result.add(new int[]{start, end});
        }

        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }

    return result.toArray(new int[result.size()][]);
}