Interval List Intersections

How it works

Since both interval lists are sorted and disjoint within themselves, we can use two pointers to efficiently find intersections. At each step, we compare the current interval from each list. If they overlap, we record the intersection. Then we advance the pointer for whichever interval ends first, since that interval cannot intersect with any future intervals from the other list. This eliminates unnecessary comparisons and processes each interval exactly once.

Steps

1. Initialize two pointers i and j to 0, and an empty result list.
2. While both pointers are within bounds:
   • Get the current intervals: [startA, endA] from firstList[i] and [startB, endB] from secondList[j].
   • Compute the potential intersection: start = max(startA, startB) and end = min(endA, endB).
   • If start <= end, add [start, end] to the result.
   • Advance the pointer for the interval that ends first (if endA < endB, increment i; otherwise, increment j).
3. Return the result list.

Complexity

• Time complexity: O(m + n)
• Space complexity:
  • O(1) extra space.
  • O(m + n) for the output list.

Where m and n are the sizes of the arrays firstList and secondList, respectively.

Things to watch for

Incorrect Overlap Detection

A common mistake is using an incorrect condition to check if two intervals overlap. The correct condition is start <= end where start = max(startA, startB) and end = min(endA, endB). Some developers mistakenly check if one interval's start is between the other's boundaries, which can miss edge cases like when intervals touch at a single point (e.g., [1,3] and [3,5] should produce [3,3]).

Wrong Pointer Advancement Logic

When using the two-pointer approach, advancing the wrong pointer leads to missed intersections. The key insight is to advance the pointer for the interval that ends first because that interval cannot intersect with any future intervals from the other list. Advancing based on start times or advancing both pointers simultaneously will produce incorrect results.

Forgetting Empty Input Cases

Failing to handle cases where one or both input lists are empty can cause index out-of-bounds errors or incorrect behavior. Always ensure your solution gracefully returns an empty result when either firstList or secondList is empty, which the two-pointer approach handles naturally by never entering the while loop.

from typing import List

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        res = []
        i = j = 0
        while i < len(firstList) and j < len(secondList):
            startA, endA = firstList[i]
            startB, endB = secondList[j]

            start = max(startA, startB)
            end = min(endA, endB)

            if start <= end:
                res.append([start, end])

            if endA < endB:
                i += 1
            else:
                j += 1

        return res

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> res;
        int i = 0, j = 0;

        while (i < firstList.size() && j < secondList.size()) {
            int startA = firstList[i][0], endA = firstList[i][1];
            int startB = secondList[j][0], endB = secondList[j][1];

            int start = max(startA, startB);
            int end = min(endA, endB);

            if (start <= end) {
                res.push_back({start, end});
            }

            if (endA < endB) {
                i++;
            } else {
                j++;
            }
        }

        return res;
    }
};