Skip to main content

Interval List Intersections

Question​

Given two lists of closed intervals, find the intersection of these two lists and return a list of the intersecting intervals.

Example 1
None

Solution​

all//Interval List Intersections.py


def intervalListIntersections(A, B):
   #store the intersection intervals
   result = []

   # Pointers to keep track of the current interval of each list
   i = 0
   j = 0

   # Iterate until either of the pointers reaches the end of their list
   while i < len(A) and j < len(B):
      # Get the current intervals of both lists
      low = max(A[i][0], B[j][0])
      high = min(A[i][1], B[j][1])

      # If the current intervals overlap, add to the result
      if low <= high:
         result.append([low, high])

      # Move the pointer of the interval with the smallest end
      if A[i][1] < B[j][1]:
         i += 1
      else:
         j += 1

   return result