Interval List Intersections

Intuition

Because both lists are already sorted by start, we can compare one interval from each at a time. The overlap of two intervals is the range from the larger of the two starts to the smaller of the two ends; if that low bound does not exceed the high bound, we found a genuine intersection. After checking a pair, the interval that finishes earlier can never intersect anything further ahead, so we discard it by moving its pointer forward. This keeps a single forward sweep over both lists.

Algorithm walkthrough

1. 1Set a pointer i for the first list and j for the second, both starting at zero.
2. 2While both pointers are in range, take lo as the max of the two starts and hi as the min of the two ends.
3. 3If lo is less than or equal to hi, push [lo, hi] onto the result since it is a real overlap.
4. 4Move forward the pointer whose current interval has the smaller end value.
5. 5Stop when either list is exhausted and return the collected intersections.

Implementation

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        result = []
        i, j = 0, 0
        while i < len(firstList) and j < len(secondList):
            lo = max(firstList[i][0], secondList[j][0])
            hi = min(firstList[i][1], secondList[j][1])
            if lo <= hi:
                result.append([lo, hi])
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        return result