Description
Cars travel toward target from distinct starting positions, each at its given positive speed. They cannot pass; cars that meet form a fleet moving at the slower speed. Count fleets arriving at target, including cars that meet exactly there.
Solution
def car_fleet(target, position, speed):
fleets = 0
latest = -1.0
for place, velocity in sorted(zip(position, speed), reverse=True):
arrival = (target - place) / velocity
if arrival > latest:
fleets += 1
latest = arrival
return fleetsExamples
Example 1
- Input
[12,[10,8,0,5,3],[2,4,1,1,3]]- Output
3
The cars form three groups before or at the destination.
Example 2
- Input
[10,[3],[3]]- Output
1
One car is one fleet.
Example 3
- Input
[10,[0,4],[2,1]]- Output
1
The rear car catches the front car before target.
Approach
Sort cars by decreasing position. Compare each car's time to reach target with the fleet ahead. A time no greater than that fleet's time means it catches up; otherwise it begins a new fleet.
Time & space
O(n log n) time and O(n) auxiliary space, where n is the car count.