Intersections of Two Interval Lists
Problem statement
Given two sorted lists of pairwise disjoint closed intervals, first and second, return every nonempty intersection in increasing start order.
A closed interval [start, end] includes both endpoints. Intersections consisting of one point must be included. Return an empty array when either input is empty or no pair overlaps. Do not change the inputs.
Function
intervalIntersections(first: int[][], second: int[][]) → int[][]Examples
Example 1
first = [[1,4],[7,10]]second = [[3,7],[9,11]]return = [[3,4],[7,7],[9,10]]The first pair shares [3,4]. The second interval in first meets the first interval in second at 7, and shares [9,10] with its second interval. Closed endpoints make [7,7] a valid intersection.
Example 2
first = [[2,5]]second = [[5,8]]return = [[5,5]]Both intervals contain the endpoint 5, so their intersection is the single point [5,5].
Example 3
first = []second = [[1,3]]return = []An empty interval list contains no points, so there are no intersections.
Constraints
- Each of
firstandsecondcontains between0and1000intervals. - Every interval contains exactly two integers between
0and1000000000, inclusive. - Each interval has
start < end. Within each list, the previous end is strictly less than the next start.