Museum Climate Dial Schedules
Count integer sequences in intervals by final value with bounded changes
A museum is planning the daily settings of a climate dial for a temporary exhibition. The dial has integer settings from 0 through ceiling, inclusive.
For each day i, bands[i] = [low, high] gives the inclusive range of settings permitted that day. Between consecutive days, the setting may change by at most ramp: if the settings are x and y, they must satisfy abs(x - y) <= ramp.
A schedule chooses exactly one setting for every day. There is no setting before the first day, so the first day's choice has no transition restriction. Two schedules are different if they choose different settings on at least one day.
Return an array of length ceiling + 1. Its entry at index v must be the number of valid schedules whose final-day setting is v, modulo 1,000,000,007. If no valid schedule ends at a setting, its entry is zero.
Examples
Example 1
Input: bands = [[0,1],[1,2]], ceiling = 3, ramp = 1 Output: [0,2,1,0]
The first day permits settings 0 and 1. The second day permits 1 and 2. With a ramp limit of 1, both first-day choices can lead to final setting 1, but only first-day setting 1 can lead to final setting 2.
Example 2
Input: bands = [[1,3],[0,2],[2,4]], ceiling = 4, ramp = 0 Output: [0,0,1,0,0]
A ramp limit of zero forces the dial to stay at the same setting throughout the exhibition. Only settings permitted by every day's band can produce a schedule.
Example 3
Input: bands = [[0,0],[4,4],[1,3]], ceiling = 4, ramp = 2 Output: [0,0,0,0,0]
The first day requires setting 0 and the next day requires setting 4. That change exceeds the ramp limit, so there are no valid schedules.
Constraints
- 1 <= bands.length <= 3000
- 0 <= ceiling <= 400
- 0 <= ramp <= ceiling
- Each entry of bands contains exactly two integers [low, high].
- 0 <= low <= high <= ceiling
The intended solution runs in O(bands.length * (ceiling + 1)) time and uses O(ceiling + 1) auxiliary space. Counts must be reduced modulo 1,000,000,007 throughout the computation.
Hints
Show hint 1Hint 1
Track how many valid schedules for the days processed so far end at each possible dial setting.
Show hint 2Hint 2
For a new setting v, the allowed previous settings form one contiguous interval. Prefix sums can obtain the total for that interval in constant time.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you compute only the total number of valid schedules, regardless of the final setting?
- How would the transition change if each day had its own ramp limit?
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