Interval List Intersections

The problem involves two lists of closed intervals, firstList and secondList, where each interval is represented as [start, end]. The intervals within a list are pairwise disjoint and sorted. The task is to find the intersection of these two interval lists.

Solution

To find the intersection, we’ll use two pointers, one for each list, and iterate through both lists simultaneously, comparing intervals from each list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        i, j = 0, 0
        result = []

        while i < len(firstList) and j < len(secondList):
            # Find the intersection between the current intervals of both lists
            start_max = max(firstList[i][0], secondList[j][0])
            end_min = min(firstList[i][1], secondList[j][1])

            # If the start is less than or equal to the end, an intersection exists
            if start_max <= end_min:
                result.append([start_max, end_min])

            # Move to the next interval in the appropriate list
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1

        return result

Explanation

• i and j are pointers for the current interval in firstList and secondList, respectively.
• We loop through both lists simultaneously until we reach the end of either list.
• We find the start and end of the intersection using max and min functions.
• If an intersection exists, we add it to the result.
• We increment the pointer for the list whose current interval ends first.
• Finally, we return the result, which is a list of intersecting intervals.

This code efficiently computes the intersection of two lists of intervals and returns the result in the required format.