You start at position 0 of a straight street and travel right until you reach position finish (finish >= 1). Shared electric scooters are parked at the distinct integer positions in scooters (in no particular order). Every scooter has enough battery for 10 units of travel.
You follow these rules exactly:
- While on foot, you walk right. Whenever you are on foot at a position where an unused scooter is parked (including position
0, and including the spot where a previous ride just ended), you take it. - You ride it right until it has covered 10 units or you reach
finish, whichever comes first. You ignore any scooters you pass during the ride. - You leave the scooter where the ride ends and continue on foot.
Write scooter_distance(finish: int, scooters: list[int]) -> int that returns the total distance you travel on scooters.
scooter_distance(23, [7, 4, 14, 20])
# 19: walk 0->4, ride 4->14 (passing 7), take the scooter at 14 and ride 14->23 (passing 20)
scooter_distance(5, [0]) # 5 (the battery would last longer, but the street ends)
scooter_distance(12, [15]) # 0 (the only scooter is beyond the finish)
scooter_distance(30, []) # 0
Constraints: 1 <= finish <= 10**9, up to 10**5 scooters with 0 <= scooters[i] <= 10**9. Stepping along the street one unit at a time is far too slow for a long street.
Show hint
Sort the scooters. Keep your current position pos; the next scooter you take is the first one at or after pos (a binary search, or a pointer that only moves forward). If it is at or beyond finish, you're done; otherwise add min(10, finish - s) and jump to the end of that ride.