Solar Brush Dispatch
Lexicographically smallest optimal fixed-width interval counts for array demands
A solar farm has a straight row of panels indexed from 0 to n - 1. Panel i needs at least demands[i] brush passes.
A cleaning robot can begin a run at any integer index s from 0 through n - width. Each run gives exactly one brush pass to every panel from s through s + width - 1. The robot may repeat the same run any number of times. Extra brush passes are allowed, and runs cannot extend beyond the row.
Return an array runs of length n - width + 1, where runs[s] is the number of runs beginning at index s.
The returned plan must satisfy every panel's demand while minimizing the total number of runs. If several minimum-total plans exist, return the lexicographically smallest runs array: at the first index where two arrays differ, prefer the array with the smaller value.
Examples
Example 1
Input: demands = [2,0,3,1,2], width = 3 Output: [2,0,2]
Runs can begin at indices 0, 1, and 2. Two runs beginning at 0 are necessary for the first panel. Two more beginning at 2 satisfy the remaining demands. Moving either of those later runs to index 1 would make the plan lexicographically larger.
Example 2
Input: demands = [0,1,0,3], width = 3 Output: [0,3]
Runs can begin only at indices 0 and 1. Three runs beginning at index 1 cover the last panel and also satisfy the other nonzero demand. No run beginning at index 0 is needed.
Example 3
Input: demands = [3,0,2], width = 1 Output: [3,0,2]
The brush is one panel wide, so each panel must receive its own runs. There is only one minimum-total plan.
Constraints
- 1 <= demands.length <= 5000
- 0 <= demands[i] <= 1000000000
- 1 <= width <= demands.length
- All inputs are integers.
The total number of runs can exceed a 32-bit integer. Python integers and JavaScript Number values are sufficient under these constraints. The brute-force verifier enumerates run counts on tiny inputs and handles width-one and whole-row brushes directly, without iterating up to a large demand.
Hints
Show hint 1Hint 1
Process panels from left to right. If a panel still needs passes, where is the latest legal start that can cover it?
Show hint 2Hint 2
Track when previously scheduled runs stop covering the row using a difference array, rather than updating every panel covered by a run.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you prove that shifting a needed run to the latest legal start cannot make the optimal total worse?
- How would the problem change if extra brush passes were forbidden?
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