FastPrepClosed Interval Overlap Queries

Closed Interval Overlap Queries

Netflix logoNetflix● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

You are given an array of closed integer intervals [start, end] and an array of query points.

Return an integer array whose first value is the maximum number of intervals that cover any point. For each query point in input order, append the number of intervals that contain that point.

An interval [start, end] contains a point x when start <= x <= end. Duplicate intervals and duplicate query points are counted independently.

Function

analyzeIntervals(intervals: int[][], queryPoints: int[]) → int[]

Examples

Example 1

intervals = [[1,3],[2,5],[5,7]]queryPoints = [1,5,6]return = [2,1,2,1]

The maximum overlap is 2. Point 1 is in one interval, endpoint 5 is in two closed intervals, and point 6 is in one.

Example 2

intervals = [[0,0],[0,0],[-2,2],[2,4]]queryPoints = [0,2,5,0]return = [3,3,2,0,3]

Both point intervals and [-2,2] cover 0, producing the maximum 3. Closed endpoint 2 belongs to two intervals.

Example 3

intervals = [[-10,-5],[1,2],[4,9]]queryPoints = [-6,0,9]return = [1,1,0,1]

The intervals are disjoint, so the maximum overlap is 1. The middle query lies in no interval.

Constraints

  • 1 <= intervals.length <= 2 * 10^5
  • 0 <= queryPoints.length <= 2 * 10^5
  • intervals[i].length == 2
  • -10^9 <= intervals[i][0] <= intervals[i][1] <= 10^9
  • -10^9 <= queryPoints[i] <= 10^9

More Netflix problems

See Netflix hiring insights
public int[] analyzeIntervals(int[][] intervals, int[] queryPoints) {
  // write your code here
}
intervals[[1,3],[2,5],[5,7]]
queryPoints[1,5,6]
expected[2,1,2,1]
Checking account…