Problems
Intervals Intersection
Medium·Tagsarraytwo-pointers
Problem Statement
Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.
The intersection of two intervals is an interval that represents the time they overlap. For example, the intersection of `
[1, 3]` and `[2, 5]` is `[2, 3]`.Examples
Example 1
Input
arr1: [[1, 3], [5, 6], [7, 9]], arr2: [[2, 3], [5, 7]]Timeline
Output
"[[2, 3], [5, 6], [7, 7]]"Why
The overlapping segments are [2, 3], [5, 6], and [7, 7] (which represents a point in time where the intervals touch).
Example 2
Input
arr1: [[1, 3], [5, 7], [9, 12]], arr2: [[5, 10]]Timeline
Output
"[[5, 7], [9, 10]]"Why
The interval [5, 10] intersects with [5, 7] entirely, and partially intersects with [9, 12].
Constraints
- •0 <= arr1.length, arr2.length <= 1000
- •arr1[i].length == 2, arr2[i].length == 2
- •0 <= start <= end <= 1000000
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
Since both lists are already sorted and their individual intervals are disjoint, you can use a Two Pointers approach. Start one pointer at the beginning of `arr1` and another at the beginning of `arr2`.
Hint 2
Two intervals `A` and `B` intersect if `max(A.start, B.start) <= min(A.end, B.end)`.
Hint 3
If they intersect, the overlapping segment is exactly `[max(A.start, B.start), min(A.end, B.end)]`.
Hint 4
After checking the current pair, which pointer should you move forward? You should always move the pointer that points to the interval with the *earlier* end time, because that interval has been fully processed.