Interval List Intersections

medium array two pointers

Problem

Given two lists of pairwise-disjoint sorted closed intervals A and B, return their list of pairwise intersections.

InputA=[[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]]

Two pointers; intersection = [max(a0,b0), min(a1,b1)] when that range is valid.

A (intervals as a-b, comma list)

B (intervals as a-b, comma list)

def intervalIntersection(A, B):
    i = j = 0
    res = []
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi: res.append([lo, hi])
        if A[i][1] < B[j][1]: i += 1
        else: j += 1
    return res

function intervalIntersection(A, B) {
  const res = []; let i = 0, j = 0;
  while (i < A.length && j < B.length) {
    const lo = Math.max(A[i][0], B[j][0]);
    const hi = Math.min(A[i][1], B[j][1]);
    if (lo <= hi) res.push([lo, hi]);
    if (A[i][1] < B[j][1]) i++; else j++;
  }
  return res;
}

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> res = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int lo = Math.max(A[i][0], B[j][0]);
            int hi = Math.min(A[i][1], B[j][1]);
            if (lo <= hi) res.add(new int[]{ lo, hi });
            if (A[i][1] < B[j][1]) i++; else j++;
        }
        return res.toArray(new int[0][]);
    }
}

vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    vector<vector<int>> res;
    int i = 0, j = 0;
    while (i < (int)A.size() && j < (int)B.size()) {
        int lo = max(A[i][0], B[j][0]);
        int hi = min(A[i][1], B[j][1]);
        if (lo <= hi) res.push_back({lo, hi});
        if (A[i][1] < B[j][1]) i++; else j++;
    }
    return res;
}

Explanation

Both lists are already sorted, so we can find every overlap with a two-pointer walk using pointers i into list A and j into list B, never going backward.

The overlap of A[i] and B[j] is [max(starts), min(ends)]. If that low end is <= the high end, the range is real and we add it to the result; otherwise the two intervals don't touch.

Then we advance whichever interval ends first (if A[i][1] < B[j][1] then i++ else j++). The one that ends sooner can't overlap anything later, so it is safe to retire it.

Example: A[1]=[5,10] and B[0]=[1,5] overlap at [max(5,1), min(10,5)] = [5,5]. Since B ends first, we move j forward and continue.

Each step throws away exactly one interval, so we touch every interval once and the lists are processed in linear time.

Time: O(n + m) Space: O(n + m)