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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Interval List Intersections

Number: 1028

Difficulty: Medium

Paid? No

Companies: Meta, Google, Amazon, Uber, Yandex, Microsoft, Verkada, Bloomberg, Adobe, DoorDash

Problem Description

Given two lists of disjoint intervals sorted by starting times, firstList and secondList, the task is to find their intersections. An intersection of two intervals is defined as a closed interval where the intervals overlap. Return a list of all such intersections.

Key Insights

  • Use two pointers to traverse both lists simultaneously.
  • Determine the overlapping interval by taking the maximum of the start points and the minimum of the end points.
  • If the overlapping condition (start <= end) is met, add the intersection to the result.
  • Move the pointer that has the smaller end value to explore further potential intersections efficiently.
  • Achieve an overall time complexity of O(m+n), where m and n are the lengths of the two interval lists.

Space and Time Complexity

Time Complexity: O(m + n) where m and n are the lengths of firstList and secondList respectively. Space Complexity: O(1) extra space (excluding the space used for the output).

Solution

The solution uses a two pointers approach. Initialize two indices, one for each list, and iterate through both lists. For each pair of intervals, the potential intersection is computed by:

  • Calculating the maximum of the two start values.
  • Calculating the minimum of the two end values. If the maximum start is less than or equal to the minimum end, there is an intersection, and it is added to the result list. The pointer corresponding to the interval with the smaller end value is then incremented since that interval cannot intersect with any further intervals from the other list. This process repeats until one of the lists is fully traversed.

Code Solutions

# Function to compute the interval intersections using two pointers
def intervalIntersection(firstList, secondList):
    intersections = []  # List to store the resulting intersections
    i, j = 0, 0  # Pointers for firstList and secondList
    
    # Loop until either list is fully traversed
    while i < len(firstList) and j < len(secondList):
        start1, end1 = firstList[i]
        start2, end2 = secondList[j]
        
        # Find the intersection boundaries
        start_overlap = max(start1, start2)
        end_overlap = min(end1, end2)
        
        # Check if there is an intersection
        if start_overlap <= end_overlap:
            intersections.append([start_overlap, end_overlap])
        
        # Move the pointer that has the smaller interval ending
        if end1 < end2:
            i += 1
        else:
            j += 1
    
    return intersections

# Example usage:
firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(firstList, secondList))  # Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
← Back to All Questions