FastPrep
Problem · Sorting

Closed Interval Overlap Queries

Learn this problem
● MediumNetflix logoNetflixFULLTIMEONSITE INTERVIEW

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

drafts saved locally
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