We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Interval List Intersections

Difficulty: Medium

Problem Description

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval.

Key Insights

  • Intervals are sorted and disjoint, which allows for efficient traversal with a two-pointer technique.
  • An intersection occurs when the end of one interval is greater than or equal to the start of the other interval.
  • The intersection's start will be the maximum of the two starts, and the end will be the minimum of the two ends.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the lengths of firstList and secondList, respectively.
Space Complexity: O(min(n, m)), for storing the resulting intersections.

Solution

The problem can be solved using a two-pointer approach. We maintain two pointers, one for each list. At each step, we compare the intervals pointed to by the pointers. If they intersect, we calculate the intersection and store it. We then move the pointer that has the interval with the smaller end. If there is no intersection, we simply move the pointer of the interval that ends first. This process continues until we have traversed both lists.

Code Solutions

def intervalIntersection(firstList, secondList):
    result = []
    i, j = 0, 0
    
    while i < len(firstList) and j < len(secondList):
        # Find the intersection between firstList[i] and secondList[j]
        start1, end1 = firstList[i]
        start2, end2 = secondList[j]
        
        # Check if they intersect
        if end1 >= start2 and end2 >= start1:
            # Add the intersection to the result
            result.append([max(start1, start2), min(end1, end2)])
        
        # Move the pointer that points to the interval that ends first
        if end1 < end2:
            i += 1
        else:
            j += 1
    
    return result
← Back to All Questions