Interval List Intersections - Leetcode Solution

Problem description:

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 is either empty or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example:

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

Solution:

The problem can be solved by iterating through both the lists simultaneously, and computing the intersection of the current interval pairs.

To compute the intersection of two intervals, we take the maximum of their start points as the start point of the intersection interval, and the minimum of their end points as the end point of the intersection interval.

We maintain two pointers, i and j, for the two lists. We also maintain an empty list, result, to store the intersection intervals.

We iterate as long as i and j are within their bounds. If the current interval pairs (firstList[i], secondList[j]) intersect, we append the intersection interval to the result list. We then increment the pointer for the interval that ends the earliest. If the current interval pairs do not intersect, we increment the pointer for the interval that ends the earliest.

Once we have finished iterating through the lists, we return the result list.

Here is the Python implementation:

class Solution: def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]: i, j = 0, 0 result = [] while i < len(firstList) and j < len(secondList): start = max(firstList[i][0], secondList[j][0]) end = min(firstList[i][1], secondList[j][1]) if start <= end: result.append([start, end]) if firstList[i][1] < secondList[j][1]: i += 1 else: j += 1 return result

Time Complexity: O(m+n), where m and n are the lengths of the two input lists.

Space Complexity: O(1), as we are only using constant space to keep track of pointers and result list.

1