Interval List Intersections
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
firstList and secondList are lists of closed intervals. Within each list, intervals are pairwise disjoint and sorted by start.
Return every nonempty intersection between an interval from the first list and an interval from the second list, in sorted order. Endpoint-only overlap is a valid one-point interval.
Function
intervalListIntersections(firstList: int[][], secondList: int[][]) → int[][]Examples
Example 1
firstList = [[0,2],[5,10]]secondList = [[1,5],[8,12]]return = [[1,2],[5,5],[8,10]]The intervals overlap at [1,2], the shared endpoint 5, and [8,10].
Example 2
firstList = []secondList = [[1,3]]return = []An empty list has no intersections.
Example 3
firstList = [[1,7]]secondList = [[2,3],[5,6]]return = [[2,3],[5,6]]Both second-list intervals lie inside [1,7].
Constraints
0 <= firstList.length, secondList.length <= 100000.-1000000000 <= start <= end <= 1000000000.- Each list is sorted by start and internally pairwise disjoint.