986. Interval List Intersections - Detailed Explanation

Problem Statement

Description:
You are given two lists of closed intervals, firstList and secondList, where each list of intervals is:

• Pairwise disjoint (i.e. no two intervals in the same list overlap), and
• Sorted in increasing order by their start time.

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

Return the intersection of these two interval lists. A common interval between two intervals [a, b] and [c, d] is a closed interval [max(a, c), min(b, d)]. If there is no intersection between two intervals, then there is no common interval.

Examples:

1. Example 1:

   • 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]]
     

   • Explanation:
     • The intersection between [0,2] and [1,5] is [1,2].
     • The intersection between [5,10] and [1,5] is [5,5].
     • The intersection between [5,10] and [8,12] is [8,10].
     • The intersection between [13,23] and [15,24] is [15,23].
     • The intersection between [24,25] and [15,24] is [24,24].
     • The intersection between [24,25] and [25,26] is [25,25].

2. Example 2:

   • Input:

     firstList = [[1,3],[5,9]]
     secondList = []
     

   • Output: []
   • Explanation:
     Since the second list is empty, there are no intersections.

Constraints:

• (0 \leq \text{firstList.length}, \text{secondList.length} \leq 1000)
• (firstList[i].length == secondList[j].length == 2)
• (0 \leq \text{start}_i \leq \text{end}_i \leq 10^9)
• Both firstList and secondList are sorted by their start times.
• Intervals in each list are disjoint.

Hints

• Hint 1:
  Since both lists are sorted and the intervals within each list do not overlap, you can use a two-pointer approach to efficiently traverse both lists in a single pass.

• Hint 2:
  For any two intervals, the intersection (if it exists) is given by: [ [\max(\text{start1}, \text{start2}), \min(\text{end1}, \text{end2})] ] Check if (\max(\text{start1}, \text{start2}) \leq \min(\text{end1}, \text{end2})) to determine if an intersection exists.

Approaches

Approach 1: Brute Force (Not Optimal)

Explanation

• Idea:
  For every interval in the first list, check it against every interval in the second list and compute the intersection if it exists.

• Complexity:
  This approach would run in (O(m \times n)) where (m) and (n) are the number of intervals in firstList and secondList, respectively. Although acceptable for small inputs, it is not optimal given that both lists can have up to 1000 intervals.

Approach 2: Two-Pointer Technique (Optimal)

Explanation

1. Initialize Two Pointers:

   • Let pointer i start at the beginning of firstList.
   • Let pointer j start at the beginning of secondList.

2. Traverse Both Lists:

   • For each pair of intervals (firstList[i] and secondList[j]), determine if they intersect by computing:
     • ( \text{startIntersection} = \max(\text{firstList}[i][0], \text{secondList}[j][0]) )
     • ( \text{endIntersection} = \min(\text{firstList}[i][1], \text{secondList}[j][1])
   • If ( \text{startIntersection} \leq text{endIntersection} ), add the intersection ([\text{startIntersection}, text{endIntersection}]) to the result.

3. Move the Pointer:

   • Move the pointer that has the interval with the smaller endpoint since that interval is finished (cannot intersect with further intervals from the other list).

4. Stop When One List is Exhausted:

   • The process stops when either pointer goes beyond the end of its list.

Pseudocode

function intervalIntersection(firstList, secondList):
    result = []
    i = 0, j = 0
    while i < length(firstList) and j < length(secondList):
        start1, end1 = firstList[i]
        start2, end2 = secondList[j]
        
        startIntersection = max(start1, start2)
        endIntersection = min(end1, end2)
        
        if startIntersection <= endIntersection:
            result.append([startIntersection, endIntersection])
        
        if end1 < end2:
            i += 1
        else:
            j += 1
    
    return result

Code Examples

Python Code