Problem

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Examples

Example 1:

gantt
    title Intervals
    dateFormat X
    axisFormat %s
    section List 1
    0-2  : 0, 2
    5-10  : 5, 10
    13-23 : 13, 23
    24-25 : 24, 25
    section List 2
    1-5  : 1, 5
    8-12  : 8, 12
    15-24 : 15, 24
    25-26 : 25, 26
    section Output
    1-2  : done, 1, 2
    5-5  : done,5, 5
    8-10  : done,8, 10
    15-23 : done,15, 23
    24-24 : done,24, 24
    25-25 : done,25, 25
  
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Example 2:

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []

Constraints:

  • 0 <= firstList.length, secondList.length <= 1000
  • firstList.length + secondList.length >= 1
  • 0 <= starti < endi <= 109
  • endi < starti+1
  • 0 <= startj < endj <= 109
  • endj < startj+1

Solution

Method 1 - Using two Pointer Technique

This problem adheres to the Merge Intervals Problem pattern. As mentioned under Insert Interval, there are five possible interactions between intervals ‘a’ and ‘b’:

  1. ‘a’ and ‘b’ do not overlap.
  2. ‘a’ and ‘b’ overlap, with ‘b’ starting within ‘a’ and ending after ‘a’.
  3. ‘a’ and ‘b’ overlap, such that ‘b’ entirely lies within ‘a’ (i.e., ‘a’ engulfs ‘b’).
  4. ‘a’ and ‘b’ overlap, with ‘a’ starting within ‘b’ and ending after ‘b’.
  5. ‘a’ and ‘b’ overlap, such that ‘a’ entirely lies within ‘b’ (i.e., ‘b’ engulfs ‘a’).

In cases 2-5, there is an overlap, where one interval’s start time falls within the other interval. This insight helps in identifying overlapping intervals.

When intervals overlap, the overlapped part can be derived by:

start = max(a.start, b.start)
end = min(a.end, b.end)

The overlap is defined by the latest start time and the earliest end time. To find intersecting intervals, we iterate through both lists, check for overlaps, and if found, append the intersecting part to the result list. We then advance the pointer of the interval that ends first.

Here is the approach:

  1. Use two pointers to traverse the two lists of intervals.
  2. At each step, determine if the intervals intersect by comparing their start and end points.
  3. If they do intersect, add the intersecting interval to the result list.
  4. Move the pointer of the interval which ends first.

Code

Java
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> ans = new ArrayList<>();
        int i = 0, j = 0;
        
        while (i < firstList.length && j < secondList.length) {
            int startMax = Math.max(firstList[i][0], secondList[j][0]);
            int endMin = Math.min(firstList[i][1], secondList[j][1]);

            if (startMax <= endMin) {
                ans.add(new int[]{startMax, endMin});
            }

            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        
        return ans.toArray(new int[ans.size()][]);
    }
}
Python
class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        ans: List[List[int]] = []
        i, j = 0, 0
        
        while i < len(firstList) and j < len(secondList):
            start_max = max(firstList[i][0], secondList[j][0])
            end_min = min(firstList[i][1], secondList[j][1])

            if start_max <= end_min:
                ans.append([start_max, end_min])
            
            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(m + n), where m and n are the lengths of the two lists.
  • 🧺 Space complexity: O(min(m, n)), for storing the result array.