Interval List Intersections

For two arrays of closed intervals given as input, intervalListA and intervalListB, where each interval has its own start and end time, write a function that returns the intersection of the two interval arrays.

For two arrays of closed intervals given as input, intervalListA and intervalListB, where each interval has its own start and end time, write a function that returns the intersection of the two interval arrays.

Statement

For example, the intersection of [3, 8] and [5, 10] is [5, 8].

Constraints

• 0 ≤ intervalListA.length, intervalListB.length ≤ 1000
• 0 ≤ start[i] < end[i] ≤ 10⁹, where i is used to indicate intervalListA
• end[i] < start[i + 1]
• 0 ≤ start[j] < end[j] ≤ 10⁹, where j is used to indicate intervalListB
• end[j] < start[j + 1]

Examples

Example 1

Input:

• intervalListA = [[1, 4], [5, 8], [9, 12]]
• intervalListB = [[2, 3], [6, 10]]

Explanation:

• [1, 4] ∩ [2, 3] = [2, 3]
• [5, 8] ∩ [6, 10] = [6, 8]
• [9, 12] has no overlap with any interval in intervalListB.

Output: [2, 3], [6, 8]

Example 2

Input:

• intervalListA = [[3, 8], [10, 15]]
• intervalListB = [[5, 10], [12, 20]]

Explanation:

• [3, 8] ∩ [5, 10] = [5, 8]
• [10, 15] ∩ [12, 20] = [12, 15]

Output: [5, 8], [12, 15]

Solution

The steps to solve this problem:

• We use two pointers, i and j. Pointer i moves through the first interval list. Pointer j moves through the second interval list.
• At each step, we look at the current interval from both lists:
  • We take the larger of the two starting points. This is the possible start of the intersection.
  • We take the smaller of the two ending points. This is the possible end of the intersection.
• If the start value is less than or equal to the end value, we have found a real intersection. We add it to our result list.
• Then, we move forward. We move the pointer for whichever interval ends earlier. This lets us check the next possible overlap.

Code

// Function to find the intersecting points between two intervals
function intervalsIntersection(intervalListA, intervalListB) {
  let intersections = []; // to store all intersecting intervals

  // index 'i' for iterating over the list 'a'
  // index 'j' for iterating over the list 'b'
  let i = 0,
      j = 0;

  while (i < intervalListA.length && j < intervalListB.length) {
    // Check if intervalListA[i] intersects intervalListB[j]

    // 1. start: The possible start point of the intersection
    let start = Math.max(intervalListA[i][0], intervalListB[j][0]);

    // 2. end: The possible end point of the intersection
    let end = Math.min(intervalListA[i][1], intervalListB[j][1]);

    // The actual intersection
    if (start <= end) intersections.push([start, end]);

    // Move forward in the list whose interval ends earlier
    if (intervalListA[i][1] < intervalListB[j][1]) i++;
    else j++;
  }

  return intersections;
}