Interval List Intersections

Naive Solution

A brute-force approach would involve iterating through all possible pairs of intervals, one from firstList and one from secondList, and checking if they intersect. If they do, compute the intersection and add it to the result.

Code (Python)

def intervalIntersection_brute_force(firstList, secondList):
    result = []
    for i in range(len(firstList)):
        for j in range(len(secondList)):
            start1, end1 = firstList[i]
            start2, end2 = secondList[j]
            
            # Check for intersection
            if start1 <= end2 and start2 <= end1:
                intersection_start = max(start1, start2)
                intersection_end = min(end1, end2)
                result.append([intersection_start, intersection_end])
    return result

Big O Analysis

• Time Complexity: O(m*n), where 'm' is the length of firstList and 'n' is the length of secondList. This is because we are iterating through all possible pairs of intervals.
• Space Complexity: O(k), where 'k' is the number of intersecting intervals. In the worst case, this could be O(m*n), but usually less.

Optimal Solution

A more efficient solution leverages the fact that both lists are sorted and disjoint. We can use a two-pointer approach. We maintain two pointers, one for each list, and advance the pointers based on the interval endpoints.

Algorithm

1. Initialize two pointers, i and j, to 0 for firstList and secondList respectively.
2. While both i and j are within the bounds of their respective lists:
   • Let start1, end1 be the start and end of firstList[i] and start2, end2 be the start and end of secondList[j].
   • Compute the intersection: intersection_start = max(start1, start2) and intersection_end = min(end1, end2).
   • If intersection_start <= intersection_end, then an intersection exists. Add [intersection_start, intersection_end] to the result.
   • Advance the pointer of the interval that ends earlier. If end1 < end2, increment i. Otherwise, increment j.
3. Return the result.

Code (Python)

def intervalIntersection(firstList, secondList):
    result = []
    i, j = 0, 0
    
    while i < len(firstList) and j < len(secondList):
        start1, end1 = firstList[i]
        start2, end2 = secondList[j]
        
        # Compute intersection
        intersection_start = max(start1, start2)
        intersection_end = min(end1, end2)
        
        if intersection_start <= intersection_end:
            result.append([intersection_start, intersection_end])
        
        # Advance the pointer of the interval that ends earlier
        if end1 < end2:
            i += 1
        else:
            j += 1
            
    return result

Big O Analysis

• Time Complexity: O(m + n), where 'm' is the length of firstList and 'n' is the length of secondList. This is because, in the worst case, we iterate through both lists once.
• Space Complexity: O(k), where 'k' is the number of intersecting intervals. In the worst case, this could be O(min(m, n)), but it depends on the input.

Edge Cases

• Empty Lists: If either firstList or secondList is empty, the intersection is empty. The algorithm handles this correctly because the while loop condition will be false immediately.
• No Intersection: If there are no intersecting intervals, the result list will be empty, which is the correct output.
• Disjoint Intervals: The algorithm correctly handles disjoint intervals by advancing the appropriate pointer when there is no overlap.