The busiest stretch of the day
A traffic chart holds one count per minute. The headline figure is the busiest run of a fixed number of consecutive minutes.
- The window is a run of exactly `runLength` consecutive minutes.
- If the day is shorter than the window, there is no such run: return 0.
- A window size of zero or less also returns 0.
busiestStretch(perMinute: list<int>, runLength: int) → int
Java needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
int busiestStretch(List<Integer> perMinute, int runLength) {
}Worked examples
| Call | Result |
|---|---|
busiestStretch(Main.<Integer>ls(1, 4, 2, 10, 2, 3, 1, 0, 20), 4) | 24 |
busiestStretch(Main.<Integer>ls(2, 3), 3) | 0 |
busiestStretch(Main.<Integer>ls(5, 5, 5), 1) | 5 |
busiestStretch(Main.<Integer>ls(1, 2, 3), 3) | 6 |
Hint
Total the first window, then slide: add the minute coming in and subtract the one going out. Re-adding the whole window each step is the slow way.
Reference solution in Java
int busiestStretch(List<Integer> perMinute, int runLength) {
if (runLength <= 0 || perMinute.size() < runLength) return 0;
int window = 0;
for (int i = 0; i < runLength; i++) window += perMinute.get(i);
int best = window;
for (int i = runLength; i < perMinute.size(); i++) {
window += perMinute.get(i) - perMinute.get(i - runLength);
if (window > best) best = window;
}
return best;
}