Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1: 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: firstList = [[1,3],[5,9]], secondList = [] Output: []

Write code to solve this problem efficiently.

## Optimal Solution: Two Pointers

This approach uses two pointers, one for each list, to iterate through the intervals in a synchronized manner. At each step, we check for overlap between the intervals pointed to by the two pointers. If they overlap, we add the intersection to the result. Then, we advance the pointer of the interval that ends earlier.

```python
 def intervalIntersection(firstList, secondList):
    result = []
    i, j = 0, 0

    while i < len(firstList) and j < len(secondList):
        # Calculate the intersection
        start_max = max(firstList[i][0], secondList[j][0])
        end_min = min(firstList[i][1], secondList[j][1])

        if start_max <= end_min:
            result.append([start_max, end_min])

        # Advance the pointer of the interval that ends earlier
        if firstList[i][1] < secondList[j][1]:
            i += 1
        else:
            j += 1

    return result

# Example Usage:
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(firstList, secondList))
# Expected Output: [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

Big(O) Run-time Analysis

The run-time complexity is O(m + n), where m and n are the lengths of firstList and secondList respectively. This is because, in the worst case, we iterate through both lists once.

Big(O) Space Usage Analysis

The space complexity is O(k), where k is the number of intersecting intervals. In the worst case, where all intervals intersect, k could be min(m, n). Therefore, the space complexity is O(min(m, n)) in the worst-case scenario. The space used by variables i and j are constant, so we can ignore it.

Edge Cases

1. Empty Lists: If either firstList or secondList is empty, the intersection is an empty list. The code handles this correctly because the while loop condition will immediately evaluate to false, and an empty list will be returned.
2. No Intersection: If there are no intersecting intervals, the result list will remain empty, which is the correct behavior.
3. Single Point Intersection: The code correctly handles cases where the intersection is a single point (e.g., [1, 2] and [2, 3] intersect at 2).
4. Complete Overlap: The code also correctly handles cases where one interval is completely contained within another (e.g., [1, 5] and [2, 3]).