FastPrep
Problem · Array

Interval List Intersections

Learn this problem
● MediumGrammarly logoGrammarlyFULLTIMEPHONE SCREEN

Problem statement

You are given two lists of closed integer intervals, firstList and secondList. Within each list, intervals are sorted by start and pairwise disjoint.

Return every nonempty intersection between an interval in firstList and an interval in secondList, ordered by increasing start. Because the input lists are internally disjoint, the returned intersections are also pairwise disjoint.

Function

intervalIntersections(firstList: int[][], secondList: int[][]) → int[][]

Examples

Example 1

firstList = [[0,2],[5,10],[13,23],[24,25]]secondList = [[1,5],[8,12],[15,24],[25,26]]return = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Each returned interval is the closed overlap of one interval from each list. Endpoint-only overlaps such as [5,5] are nonempty.

Example 2

firstList = [[1,3],[6,8]]secondList = [[4,5],[9,10]]return = []

No interval from one list overlaps an interval from the other.

Example 3

firstList = []secondList = [[2,7]]return = []

An empty list has no intersections.

Constraints

  • 0 <= firstList.length, secondList.length <= 100000.
  • Every interval has exactly two integers [start, end] with start <= end.
  • Within each list, intervals are sorted by start and satisfy intervals[i][1] < intervals[i + 1][0].
  • Every endpoint is a signed 32-bit integer.

More Grammarly problems

drafts saved locally
public int[][] intervalIntersections(int[][] firstList, int[][] secondList) {
  // Write your code here.
}
firstList[[0,2],[5,10],[13,23],[24,25]]
secondList[[1,5],[8,12],[15,24],[25,26]]
expected[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
checking account