Time Complexity: $O(N \times M)$, where $N$ and $M$ are the lengths of the two lists. Space Complexity: $O(1)$ auxiliary space (excluding output).

Why it fails: While the constraints ($N, M \le 1000$) might allow this solution to pass without a Time Limit Exceeded (TLE) error on some platforms, it is fundamentally inefficient. It performs redundant comparisons and fails to utilize the critical property that the input lists are sorted and disjoint. In a serious interview context, an $O(N \times M)$ solution for sorted inputs is considered suboptimal.

Core Insight for Interval List Intersections

The key to solving LeetCode 986 efficiently lies in the "Two Pointers" technique applied within a greedy framework. Since both lists are sorted by start time, we can iterate through them in a single pass.

The core logic revolves around how we determine the intersection and how we advance our pointers:

1. Intersection Logic: Two intervals A and B intersect if the start of the intersection window is less than or equal to the end of the intersection window. Mathematically, the intersection is [max(A.start, B.start), min(A.end, B.end)]. If max_start <= min_end, we have a valid intersection.
2. Greedy Pointer Movement: After checking for an intersection between firstList[i] and secondList[j], we must decide which pointer to advance (i or j).
   • If firstList[i] ends before secondList[j], it is impossible for firstList[i] to intersect with any subsequent intervals in secondList (because secondList is sorted). Therefore, we are finished with firstList[i] and should increment i.
   • Conversely, if secondList[j] ends before firstList[i], we increment j.

Visual Description: Imagine two horizontal timelines. We place a pointer at the beginning of each list. We look at the two current intervals. We mathematically determine the "overlap zone" based on the latest start time and the earliest end time. Once we record any overlap, we look at the endpoints. The interval that finishes earliest is "discarded" because its timeline has been fully processed relative to the current position of the other list. We move that pointer forward to bring the next interval into consideration.

Execution Flow

Let's trace firstList = [[0,2], [5,10]] and secondList = [[1,5], [8,12]].

1. Step 1: i=0 ([0,2]), j=0 ([1,5]).

   • lo = max(0, 1) = 1.
   • hi = min(2, 5) = 2.
   • lo <= hi is true. Add [1, 2] to result.
   • firstList[0].end (2) < secondList[0].end (5). Increment i.

2. Step 2: i=1 ([5,10]), j=0 ([1,5]).

   • lo = max(5, 1) = 5.
   • hi = min(10, 5) = 5.
   • lo <= hi is true. Add [5, 5] to result.
   • secondList[0].end (5) < firstList[1].end (10). Increment j.

3. Step 3: i=1 ([5,10]), j=1 ([8,12]).

   • lo = max(5, 8) = 8.
   • hi = min(10, 12) = 10.
   • lo <= hi is true. Add [8, 10] to result.
   • firstList[1].end (10) < secondList[1].end (12). Increment i.

4. Step 4: i is now 2, which equals firstList.length. Loop terminates.

Proof of Correctness

The correctness relies on the sorted and disjoint properties. When we compare interval $A$ and interval $B$, and we find that $A.end < B.end$, we claim we can safely discard $A$. Why?

Because the other list is sorted, any subsequent interval $B_{next}$ will have $B_{next}.start > B.end$. Since $A.end < B.end$, it implies $A.end < B_{next}.start$. Thus, $A$ cannot possibly overlap with $B_{next}$ or any interval after it. This guarantees that by moving the pointer of the interval ending first, we never miss a future intersection.

Reference Implementation

C++ Solution for LeetCode 986

cpp
class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        vector<vector<int>> result;
        int i = 0; // Pointer for firstList
        int j = 0; // Pointer for secondList

        while (i < firstList.size() && j < secondList.size()) {
            // Let's check if firstList[i] intersects secondList[j].
            // lo - the start of the intersection
            // hi - the end of the intersection
            int lo = max(firstList[i][0], secondList[j][0]);
            int hi = min(firstList[i][1], secondList[j][1]);

            // If lo <= hi, we have a valid intersection
            if (lo <= hi) {
                result.push_back({lo, hi});
            }

            // Remove the interval with the smallest endpoint
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }

        return result;
    }
};

Java Solution for LeetCode 986

java
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> resultList = new ArrayList<>();
        int i = 0;
        int j = 0;

        while (i < firstList.length && j < secondList.length) {
            // Find the intersection boundaries
            int lo = Math.max(firstList[i][0], secondList[j][0]);
            int hi = Math.min(firstList[i][1], secondList[j][1]);

            // If valid intersection, add to list
            if (lo <= hi) {
                resultList.add(new int[]{lo, hi});
            }

            // Advance the pointer of the interval that ends first
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }

        return resultList.toArray(new int[resultList.size()][]);
    }
}

Python Solution for LeetCode 986

python
class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        result = []
        i, j = 0, 0
        
        while i < len(firstList) and j < len(secondList):
            # Let's check if firstList[i] intersects secondList[j].
            # lo - the start of the intersection
            # hi - the end of the intersection
            lo = max(firstList[i][0], secondList[j][0])
            hi = min(firstList[i][1], secondList[j][1])
            
            # If lo <= hi, we have a valid intersection
            if lo <= hi:
                result.append([lo, hi])
            
            # Remove the interval with the smallest endpoint
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
                
        return result

• Mistake: Using strict inequality checks like if (lo < hi) instead of if (lo <= hi).
• Reasoning: Closed intervals include their endpoints. An interval ending at 5 and another starting at 5 intersect at exactly 5.
• Consequence: Correctness failure; missing valid intersections.