986. Interval List Intersections

This problem asks to find the intersection of two lists of closed intervals. Both input lists are pairwise disjoint and sorted. The solution uses a two-pointer approach for optimal efficiency.

Approach

The core idea is to iterate through both lists simultaneously using two pointers, i and j, one for each list. At each step, we compare the current intervals from both lists:

1. Find the intersection: We calculate the start and end of the intersection by taking the maximum of the two interval starts (max(firstList[i][0], secondList[j][0])) and the minimum of the two interval ends (min(firstList[i][1], secondList[j][1])). If the resulting start is less than or equal to the end (meaning there's an intersection), we add this intersection interval to the result list.

2. Advance the pointers: We advance the pointer of the interval that ends sooner. This is because any further intersections with the interval that ended earlier will not overlap with the current interval from the other list since the lists are sorted.

3. Repeat: We continue this process until one of the pointers reaches the end of its respective list.

Code Explanation (Python)

class Solution:
    def intervalIntersection(
        self, firstList: List[List[int]], secondList: List[List[int]]
    ) -> List[List[int]]:
        i = j = 0
        ans = []
        while i < len(firstList) and j < len(secondList):
            s1, e1, s2, e2 = *firstList[i], *secondList[j]  # Unpack the intervals
            l, r = max(s1, s2), min(e1, e2)  # Calculate intersection start and end
            if l <= r:  # Check for intersection
                ans.append([l, r])  # Add intersection to result
            if e1 < e2:  # Advance the pointer of the interval that ends sooner
                i += 1
            else:
                j += 1
        return ans

The Python code directly implements the algorithm described above. The * operator unpacks the nested lists into individual variables for easier readability and manipulation.

Time and Space Complexity Analysis

• Time Complexity: O(m + n), where 'm' and 'n' are the lengths of firstList and secondList respectively. We iterate through each list at most once.
• Space Complexity: O(min(m, n)) in the worst case. The size of the result list (ans) is bounded by the length of the shorter input list, as the number of intersections cannot exceed the number of intervals in the smaller list. In the best case (no intersections), it's O(1).

Code in Other Languages

The approach remains consistent across different programming languages. The provided code snippets in Java, C++, Go, TypeScript, and Rust demonstrate this. The primary differences lie in syntax and data structure handling. For instance, Java and C++ use ArrayList and vector respectively to handle dynamic resizing of the result list.

Example Walkthrough

Let's consider firstList = [[0,2],[5,10],[13,23],[24,25]] and secondList = [[1,5],[8,12],[15,24],[25,26]].

1. i = 0, j = 0: [0, 2] and [1, 5] intersect at [1, 2]. e1 < e2, so i increments.
2. i = 1, j = 0: [5, 10] and [1, 5] intersect at [5, 5]. e1 > e2, so j increments.
3. i = 1, j = 1: [5, 10] and [8, 12] intersect at [8, 10]. e1 < e2, so i increments.
4. i = 2, j = 1: [13, 23] and [8, 12] do not intersect. e1 > e2, so j increments.
5. i = 2, j = 2: [13, 23] and [15, 24] intersect at [15, 23]. e1 < e2, so i increments.
6. i = 3, j = 2: [24, 25] and [15, 24] intersect at [24, 24]. e1 < e2, so i increments.
7. i = 3, j = 3: [24, 25] and [25, 26] intersect at [25, 25]. The algorithm terminates.

The final result is [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]].