Snow Survey Synchronization Band
Narrowest integer interval meeting each sorted array's count quota
A ski resort collects snow-depth readings from several survey stations. Each station's readings have already been sorted in nondecreasing order.
You are given readings, where readings[i] contains the readings from station i, and quotas, where quotas[i] is the minimum number of readings that station must contribute.
Choose a closed integer band [low, high] such that, for every station i, at least quotas[i] entries in readings[i] lie inside the band. Repeated readings count separately.
Return [low, high] for the band with the smallest width high - low. If several bands have the same smallest width, return the one with the smallest low.
Every station has enough readings to meet its quota, so a valid band always exists.
Examples
Example 1
Input: readings = [[1,4,6,10],[2,5,9]], quotas = [2,1] Output: [4,6]
The band [4, 6] contains two readings from the first station and one from the second. No narrower band meets both quotas.
Example 2
Input: readings = [[3,3,8],[1,3,3,7]], quotas = [2,2] Output: [3,3]
The repeated readings at depth 3 count separately. A zero-width band at depth 3 satisfies both stations.
Example 3
Input: readings = [[-5,5],[-4,6]], quotas = [1,1] Output: [-5,-4]
Both [-5, -4] and [5, 6] satisfy the quotas with width 1. The smaller lower endpoint breaks the tie.
Constraints
- 1 <= readings.length <= 1000
- quotas.length == readings.length
- Each readings[i] is nonempty and sorted in nondecreasing order.
- 1 <= quotas[i] <= readings[i].length
- The total number of entries across readings is at most 10000.
- -1000000000 <= readings[i][j] <= 1000000000
The intended solution runs in O(N log(k + 1)) time and O(k) auxiliary space, where N is the total number of readings and k is the number of stations.
Hints
Show hint 1Hint 1
For one station, any feasible band contains a consecutive block of exactly that station's quota size.
Show hint 2Hint 2
Keep one quota-sized block per station. Track the smallest block start with a heap and the largest block end. Which block must advance before the current band can improve?
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the indices of one quota-sized block from each station inside the chosen band?
- How would the solution simplify if every station's quota were exactly one?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem