runtimequestion 350 Algorithms & Complexity · hard
The busiest few minutes of pickups
A taxi dispatcher wants the largest number of pickups that fall within any width seconds, to plan cover for peaks. The pickup times arrive sorted. Write busiest_window(times, width) in one pass: keep the pickups of the current window in a queue, dropping old ones from the front as time moves on.
Function
busiest_window(times, width)timespickup times in seconds since midnight, sorted ascending (repeats allowed)
Returnsthe most pickups whose times all fit in one window of
width seconds, that is, latest − earliest < width; 0 for no pickupsConstraintread each time about once: at most 3,000 reads for 1,000 times
Examples
callbusiest_window([28367, 28370, 28401, 28650, 28655, 28659, 28700], 60)returns4
callbusiest_window([28367, 28370, 28401, 28650, 28655, 28659, 28700], 10)returns3
callbusiest_window([100, 500, 900], 60)returns1