Bus Tracker Waits
EasyMath · Bloomberg
A transit display shows riders how long until the next bus. Each element of routes is [first, interval]: that route's bus departs at time first and then every interval time units after that, forever (at first, first + interval, first + 2 * interval, ...). It never departs before first.
For each time t in queries, compute the wait until the next departure of any route, where a bus departing exactly at time t means a wait of 0. In other words, for each route find the earliest departure at or after t, subtract t, and take the minimum over all routes.
Return a list with one entry per query, in query order. If routes is empty, every entry is None.
Example 1
- Input:
- routes = [[0, 15], [7, 20], [40, 5]], queries = [12, 27, 50]
- Output:
- [3, 0, 0]
- Explanation
- At 12, the first route next leaves at 15 (wait 3) and the second at 27 (wait 15); the third has not started yet and first leaves at 40 (wait 28). The best is 3. At 27 the second route leaves right then, so the wait is 0. At 50 the third route also departs exactly then.
Example 2
- Input:
- routes = [[100, 30]], queries = [0, 100, 101]
- Output:
- [100, 0, 29]
- Explanation
- Before the first departure at 100 the rider waits until 100, a wait of 100. At 100 the wait is 0, and one unit later the next bus is at 130, a wait of 29.
Example 3
- Input:
- routes = [], queries = [5]
- Output:
- [None]
- Explanation
- With no routes there is nothing to wait for, so the answer is
None.
Constraints
0 <= routes.length <= 10000 <= queries.length <= 10000 <= first <= 10^9and1 <= interval <= 10^90 <= t <= 10^9