Interval List Intersections - Video Solutions

Problem Overview: You get two lists of closed intervals. Each list is already sorted and internally non-overlapping. The task is to return all intersections between intervals from the first list and the second list.

The challenge is efficiently identifying overlapping regions between two ordered interval sequences. Since both lists are sorted by start time, you can exploit that structure instead of comparing every pair.

Approach 1: Brute Force Comparison (O(n * m) time, O(1) space)

The straightforward solution compares every interval in the first list with every interval in the second list. For each pair [a1, a2] and [b1, b2], compute the overlap using start = max(a1, b1) and end = min(a2, b2). If start <= end, an intersection exists and should be added to the result.

This approach works because interval intersection can be determined in constant time. However, you still check all possible pairs using nested loops. With n intervals in the first list and m in the second, the time complexity becomes O(n * m). Space complexity remains O(1) excluding the output. This approach is easy to implement but inefficient for large inputs.

Approach 2: Two Pointers Technique (O(n + m) time, O(1) space)

A better solution uses the two pointers pattern to scan both interval lists simultaneously. Start with pointer i at the beginning of the first list and pointer j at the beginning of the second. At each step, compare intervals A[i] and B[j].

Compute the intersection exactly the same way as the brute force method: start = max(A[i][0], B[j][0]) and end = min(A[i][1], B[j][1]). If start <= end, add the interval to the result. After checking overlap, move the pointer that has the smaller end value. This works because the interval that ends first cannot intersect with any future intervals in the other list.

Each interval is processed at most once. That reduces the runtime to O(n + m), where n and m are the sizes of the two lists. The algorithm uses only a few variables, so the extra space complexity is O(1). This technique is common in ordered data problems involving arrays and interval merging.

Recommended for interviews: Interviewers typically expect the Two Pointers solution. Starting with the brute force approach shows you understand how interval overlap works. Then optimizing to the O(n + m) two-pointer scan demonstrates algorithmic thinking and awareness of sorted input properties.