Interval List Intersections

Interval List Intersections

1. What is this problem about?

The Interval List Intersections interview question asks you to find the overlapping regions between two sets of sorted, non-overlapping intervals. For example, if List A has [0, 2] and List B has [1, 5], their intersection is [1, 2]. You need to return a new list containing all such intersections.

2. Why is this asked in interviews?

This is a standard question at Google, Uber, and Meta. It tests your ability to handle multiple sorted lists and apply Two Pointers logic to interval boundaries. It’s a core Line Sweep interview pattern that evaluations how you manage overlapping ranges without resorting to $O(N^2)$ comparisons.

3. Algorithmic pattern used

This problem follows the Two Pointers pattern.

1. Pointers: i = 0 for List A, j = 0 for List B.
2. Find Overlap: The potential intersection is [max(startA, startB), min(endA, endB)].
3. Validation: If start <= end, the intersection is valid. Add it to result.
4. Advance: Increment the pointer of the interval that ends first. If endA < endB, increment i; otherwise, increment j.

4. Example explanation

A = [[0, 2], [5, 10]], B = [[1, 5], [8, 12]]

1. i=0, j=0: [0, 2] and [1, 5]. Intersection: [max(0,1), min(2,5)] = [1, 2]. Valid. endA(2) < endB(5), so i++.
2. i=1, j=0: [5, 10] and [1, 5]. Intersection: [max(5,1), min(10,5)] = [5, 5]. Valid. endB(5) == endA(10) (well, 5 is smaller), so j++.
3. i=1, j=1: [5, 10] and [8, 12]. Intersection: [max(5,8), min(10,12)] = [8, 10]. Valid. Result: [[1, 2], [5, 5], [8, 10]].

5. Common mistakes candidates make

• Ignoring empty intersections: Forgetting that two intervals can "touch" at a single point (e.g., [1, 2] and [2, 3] intersect at [2, 2]).
• Incorrect pointer move: Not moving the pointer of the interval that ends earlier, which can skip valid intersections.
• Nested Loops: Using $O(N \cdot M)$ complexity instead of $O(N+M)$.

6. Interview preparation tip

Think of this as a zipper. You are pulling two sliders along two tracks. The min(end) logic ensures you never "jump over" a segment that could overlap with the current one. This is a vital Sorting interview pattern skill.