Maximum Intervals Overlapping a Fixed-Length Window
Booking.com● MediumFULLTIMEONSITE INTERVIEWProblem statement
You are given an array of closed time intervals. Each row [start, end] represents one interval occurrence. Equal rows still represent separate occurrences.
Choose one closed window [x, x + k], where x may be any integer. Count every input interval that has a nonempty intersection with that window. Touching at an endpoint counts, and an interval does not need to be fully contained in the window.
Return the largest possible count. When k = 0, the window is a single point. You count intervals touched anywhere in one window, even when those intervals do not overlap one another.
Function
maxOverlaps(intervals: int[][], k: int) → intExamples
Example 1
intervals = [[1,2],[4,5],[7,8]]k = 3return = 2The window [2,5] touches [1,2] at 2 and intersects [4,5]. It misses [7,8]. No length-3 window can touch both the first and third intervals because their nearest endpoints are 5 units apart.
Example 2
intervals = [[0,0],[2,2],[4,4]]k = 4return = 3The window [0,4] touches all three point intervals, including both window endpoints. Three is the total number of input intervals, so this is optimal.
Example 3
intervals = [[2,8],[3,4],[7,9]]k = 0return = 2At x = 3, the single-point window touches [2,8] and [3,4]. It cannot touch all three intervals because [3,4] and [7,9] have no point in common.
Constraints
1 <= intervals.length <= 10^5.- Every interval row has exactly
2entries. 0 <= intervals[i][j] <= 10^9.- For each row,
start <= end. 0 <= k <= 10^9.