Code Implementation

class Solution:
    def intervalIntersection(self, A, B):
        result = []
        i, j = 0, 0
        while i < len(A) and j < len(B):
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            if start <= end:
                result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
        return result
      

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        while (i < A.size() && j < B.size()) {
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            if (start <= end) {
                result.push_back({start, end});
            }
            if (A[i][1] < B[j][1]) {
                ++i;
            } else {
                ++j;
            }
        }
        return result;
    }
};
      

class Solution {
    public int[][] intervalIntersection(int[][] A, int[][] B) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
            int start = Math.max(A[i][0], B[j][0]);
            int end = Math.min(A[i][1], B[j][1]);
            if (start <= end) {
                result.add(new int[]{start, end});
            }
            if (A[i][1] < B[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}
      

var intervalIntersection = function(A, B) {
    let result = [];
    let i = 0, j = 0;
    while (i < A.length && j < B.length) {
        let start = Math.max(A[i][0], B[j][0]);
        let end = Math.min(A[i][1], B[j][1]);
        if (start <= end) {
            result.push([start, end]);
        }
        if (A[i][1] < B[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
};
      

Problem Description

You are given two lists of closed intervals, A and B, where each interval is represented as a pair [start, end]. Both lists are sorted in ascending order by their start times, and the intervals within each list do not overlap (they are disjoint).

Your task is to return the intersection of these two interval lists. An intersection between two intervals is defined as the set of points they both cover, i.e., the overlapping part. The output should be a list of intervals representing all intersections between intervals in A and intervals in B.

Key constraints:

• Each interval list is sorted and non-overlapping.
• Return all intersections in the order they appear.
• Do not reuse intervals; move forward through each list as you process them.

Thought Process

When confronted with two lists of sorted, non-overlapping intervals, the naive approach might be to compare every interval in A with every interval in B. This would work but would be inefficient, especially as the lists grow larger.

However, since both lists are sorted and intervals do not overlap within a list, we can process them efficiently using a two-pointer technique. This is similar to merging two sorted lists, where we advance through each list based on which interval ends first.

By always comparing the current intervals from both lists, we can easily determine if they overlap and, if so, what their intersection is. Then, we move forward in the list whose interval ends first, ensuring we never miss a possible intersection and never double-count any intervals.

Solution Approach

Let's break down the step-by-step strategy to solve this problem:

1. Initialize Two Pointers: Start with two pointers, i and j, both set to 0. These will track our current position in lists A and B.
2. Iterate Through Both Lists: As long as neither pointer has reached the end of its list, do the following:
   • Get the current intervals: A[i] = [startA, endA] and B[j] = [startB, endB].
   • Compute the intersection, if any: The intersection starts at max(startA, startB) and ends at min(endA, endB).
   • If the start of the intersection is less than or equal to the end, then the intervals overlap, and we add [start, end] to our result.
   • Move the pointer forward in the list whose interval ends first (i.e., if endA < endB, advance i; otherwise, advance j). This ensures we always compare the next possible overlapping intervals.
3. Return the Result: Once either pointer reaches the end of its list, all possible intersections have been found.

This approach is efficient because it leverages the sorted, non-overlapping nature of the input lists, ensuring we never do unnecessary comparisons.

Example Walkthrough

Let's use the following example:
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]

1. First Comparison:
   • A[0] = [0,2], B[0] = [1,5]
   • Intersection: start = max(0,1) = 1, end = min(2,5) = 2
   • Since 1 ≤ 2, add [1,2] to result.
   • A[0] ends first, so move i to 1.
2. Second Comparison:
   • A[1] = [5,10], B[0] = [1,5]
   • Intersection: start = max(5,1) = 5, end = min(10,5) = 5
   • Since 5 ≤ 5, add [5,5] to result.
   • B[0] ends first, so move j to 1.
3. Third Comparison:
   • A[1] = [5,10], B[1] = [8,12]
   • Intersection: start = max(5,8) = 8, end = min(10,12) = 10
   • Since 8 ≤ 10, add [8,10] to result.
   • A[1] ends first, so move i to 2.
4. Continue:
   • Repeat the process for the remaining intervals:
   • [15,23] and [13,23] → [15,23]
   • [24,24] and [24,25] → [24,24]
   • [25,25] and [25,26] → [25,25]
5. Final Result: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Time and Space Complexity

• Brute-force Approach:
  • Compare every interval in A with every interval in B.
  • Time complexity: O(N * M), where N and M are the lengths of A and B.
  • Space complexity: O(1) for extra space, plus the space needed for the result.
• Optimized Two-Pointer Approach:
  • Each pointer only moves forward, so we process each interval at most once.
  • Time complexity: O(N + M) — linear in the total number of intervals.
  • Space complexity: O(K), where K is the number of intersections found (for the output).

The optimized approach is much more efficient and scalable for large inputs.

Summary

The Interval List Intersections problem is elegantly solved using a two-pointer technique, taking advantage of the sorted and non-overlapping properties of the input lists. By always advancing the pointer whose interval ends first, we ensure that all possible intersections are found efficiently, with no unnecessary comparisons. This approach is both intuitive and optimal, making it a great example of how understanding input constraints can lead to simple, powerful algorithms.