Back to Problems

Interval List Intersections

Medium
Intervals

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.

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 are either empty or represented as a closed interval.

Key insight: Use two pointers, one for each list. For the current pair:

  • Intersection start = max(a.start, b.start)
  • Intersection end = min(a.end, b.end)
  • If start <= end, there's an intersection
  • Advance the pointer with the smaller end time

Real-world analogy: Finding overlapping availability between two people's schedules.

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]]
Explanation: Multiple intersections found by comparing intervals from both lists.

Example 2

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
Explanation: One list is empty, so there are no intersections.

Example 3

Input: firstList = [], secondList = [[4,8],[10,12]]
Output: []
Explanation: One list is empty, so there are no intersections.

Constraints

  • •0 <= firstList.length, secondList.length <= 1000
  • •firstList.length + secondList.length >= 1
  • •0 <= start_i < end_i <= 10^9
  • •0 <= start_j < end_j <= 10^9
  • •Each list is pairwise disjoint and in sorted order
Show Hints (4)
Hint 1: Use two pointers, one for each list.
Hint 2: For two intervals, the intersection is [max(start1, start2), min(end1, end2)].
Hint 3: If max(start1, start2) <= min(end1, end2), there is an intersection.
Hint 4: Advance the pointer pointing to the interval that ends first.
Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor
Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?