Find all common regions between two sorted, disjoint interval lists.
Write a function `interval_intersections(first, second)` that takes two lists of intervals. Each interval is a list `[start, end]` with `start <= end`. Each input list is sorted by start time and contains no overlapping intervals within itself. The function must return a list of intervals `[start, end]` that are present in both input intervals, i.e., the intersection (overlap) of any interval from `first` with any interval from `second`. The result must be sorted by start time and contain no duplicates. Use a two-pointer approach.
Constraints
0 <= len(first), len(second) <= 10^4. Interval endpoints are integers in [-10^6, 10^6]. The solution should run in O(len(first) + len(second)) time and O(1) extra space (excluding the output).
Example
>>> interval_intersections([[0,2],[5,10],[13,23],[24,25]], [[1,5],[8,12],[15,24],[25,26]])
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
>>> interval_intersections([[1,3],[5,9]], [])
[]
>>> interval_intersections([[1,7]], [[3,10]])
[[3,7]]
20 points
~20 min