NeetCode #835LC-986MediumIntervals
← Back to All Problems#835 · #986 · Interval List Intersections(区间列表的交集)
📌 Problem Statement & Constraints
You are given two lists of closed intervals
firstList and secondList, each sorted and internally disjoint. Return the intersection of the two lists. Constraints: 0 <= firstList.length, secondList.length <= 1000, 0 <= start <= end <= 10^9.💡 Core Algorithmic Approaches
- Use two pointers, one per list, and always advance the interval that ends first.
- The overlap of the current pair is
[max(starts), min(ends)]; it is non-empty when the lower bound does not exceed the upper bound. - After recording an overlap, move past the interval with the smaller end, since it cannot overlap any later interval of the other list.
- Both lists are sorted, so this two-pointer sweep visits each interval once.
💻 Benchmark Python3 Implementation
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
res = []
i = j = 0
while i < len(firstList) and j < len(secondList):
lo = max(firstList[i][0], secondList[j][0])
hi = min(firstList[i][1], secondList[j][1])
if lo <= hi:
res.append([lo, hi]) # non-empty overlap
if firstList[i][1] < secondList[j][1]:
i += 1 # first ends earlier -> advance it
else:
j += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m + n): each pointer advances monotonically.
💾 Space Complexity
O(1) beyond the output.
⚠️ Interview Pitfalls & Follow-ups
- Using
lo < hifor the overlap test: closed intervals sharing a single point do intersect, so the test islo <= hi. - Advancing both pointers on a match: only the earlier-ending interval is exhausted; advancing both can skip a valid intersection.
- Assuming the input is unsorted: the two-pointer sweep relies on both lists being sorted and disjoint.
- Merging the output: the intersections of two disjoint lists are themselves disjoint and already sorted, so no post-processing is needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.