Interval List Intersections

01 · Question

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.

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

02 · Solution

Reference solution

1def intervalIntersection(firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
2    i, j = 0, 0
3    res = []
4    
5    while i < len(firstList) and j < len(secondList):
6        lo = max(firstList[i][0], secondList[j][0])
7        hi = min(firstList[i][1], secondList[j][1])
8        
9        if lo <= hi:
10            res.append([lo, hi])
11            
12        if firstList[i][1] < secondList[j][1]:
13            i += 1
14        else:
15            j += 1
16            
17    return res

Squares of a Sorted Array

Merge Sorted Array