Interval List Intersections

Problem Statement

In the given problem, we are provided with two lists of closed intervals named firstList and secondList. Each entry in these lists, firstList[i] and secondList[j], represents an interval with starting point starti or startj and ending point endi or endj respectively, where the intervals are non-overlapping and stored in an ascending order based on their start points.

A closed interval [a, b] encompasses all real numbers x such that a is less than or equal to x which in turn is less than or equal to b.

The task is to determine and return the intersection of these two lists of intervals. An intersection of two intervals is defined as the common numerals that lie within both intervals. If two intervals do not overlap, their intersection is an empty set. For example, when intersecting [1, 3] and [2, 4], the interval [2, 3] is returned as they overlap over this range.

Examples

Example 1

Input:

firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

Output:

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

Example 2

Input:

firstList = [[1,3],[5,9]], secondList = []

Output:

[]

Constraints

• 0 <= firstList.length, secondList.length <= 1000
• firstList.length + secondList.length >= 1
• 0 <= starti < endi <= 109
• endi < starti+1
• 0 <= startj < endj <= 109
• endj < startj+1

Approach and Intuition

When calculating the intersection of two lists of intervals, the key idea relies on examining each interval from firstList with every appropriate interval in secondList. This involves:

1. Initializing pointers for both lists, starting at the beginning of each list.

2. Comparing the current interval from firstList with the one from secondList:

   • Evaluate the maximum of the two starting points and the minimum of the two ending points.
   • If the maximum start point is less than or equal to the minimum end point, an intersection exists and is defined by these max-min values.
   • Record this intersection if it exists.

3. Adjusting the pointers based on the comparison:

   • If the end of the current interval in firstList is less than the end of the interval in secondList, increase the pointer for firstList to the next interval.
   • Otherwise, increase the pointer for secondList.

4. Continue the above steps until one of the lists is completely traversed.

Considerations:

• If either of the initial lists is empty, the intersection is immediately known to be an empty list since there are no intervals to intersect.
• The constraints ensure us that the comparison and iterative shift process will run efficiently even for the maximum input sizes.

Using this approach, which fundamentally employs a two-pointer technique, respects both the sorted and disjoint nature of the interval lists to efficiently compute their intersection without unnecessary comparisons.

Solutions

class Solution {
  public int[][] findIntersections(int[][] FirstList, int[][] SecondList) {
    List<int[]> intersections = new ArrayList<>();
    int firstIdx = 0, secondIdx = 0;

    while (firstIdx < FirstList.length && secondIdx < SecondList.length) {
      int start = Math.max(FirstList[firstIdx][0], SecondList[secondIdx][0]);
      int end = Math.min(FirstList[firstIdx][1], SecondList[secondIdx][1]);
      if (start <= end)
        intersections.add(new int[]{start, end});

      if (FirstList[firstIdx][1] < SecondList[secondIdx][1])
        firstIdx++;
      else
        secondIdx++;
    }

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