⚡Flashcard Drill➔
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

  1. Use two pointers, one per list, and always advance the interval that ends first.
  2. 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.
  3. After recording an overlap, move past the interval with the smaller end, since it cannot overlap any later interval of the other list.
  4. 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 < hi for the overlap test: closed intervals sharing a single point do intersect, so the test is lo <= 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.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems