Interval List Intersections

LeetCode

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]]
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
Previous
Squares of a Sorted Array
Next
Merge Sorted Array
List A (i=0)
[0,2]
[5,10]
[13,23]
[24,25]
List B (j=0)
[1,5]
[8,12]
[15,24]
[25,26]
Intersection candidate (lo, hi)
[1,2]
Intersection Result
0
5
10
15
20
25
30

Logic Visualization (Step 1: Check Overlap)

A: [0, 2]
B: [1, 5]
max(start) = 1
min(end) = 2
Overlap
Logic:Compute lo=max(starts) and hi=min(ends), then check lo <= hi.
firstList=Array(4)
secondList=Array(4)
currentIntersection=null
resultList=[]
logic={ stepType, A, B, maxStart, minEnd, hasOverlap }
Step 1 / 21
Step 1:
At A[i] and B[j], compute lo=max(starts)=1 and hi=min(ends)=2. Since lo<=hi, these intervals overlap.
Pointers: i=0, j=0
Focus: compare