There are n cars traveling to the same destination on a one-lane highway.
You are given two arrays of integers position and speed, both of length n.
position[i] is the position of the ith car (in miles) speed[i] is the speed of the ith car (in miles per hour) The destination is at position target miles.
A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.
A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.
If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.
Return the number of different car fleets that will arrive at the destination.
Example 1:
Input: target = 10, position = [1,4], speed = [3,2]
Output: 1 Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination.
Example 2:
Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]
Output: 3 Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.
- Sort cars in reverse order
- Calculate dest time for each car
- If a car behind takes longer to reach the target than a car in front, it will never catch up
- If a car behind takes less time to reach the target, it will catch up and form a fleet with the car in front
- Once cars form a fleet, they must travel at the speed of the slowest car in the fleet
- Tracks current maximum time (curtime) needed for any fleet to reach target
- When it finds a car that takes longer to reach target (destination_time > curtime): - It forms a new fleet (increment fleets) Updates curtime to this new, longer time
def carFleet(target_distance, starting_positions, car_speeds):
pairs = [[starting_positions[i],car_speeds[i]] for i in range(len(starting_positions))]
fleets, slowest_time = 0, 0
for position, speed in sorted(pairs, reverse=True):
time_to_target = (target_distance-position)/speed
if time_to_target > slowest_time:
fleets+=1
slowest_time = time_to_target
return fleets
carFleet(10, [4,1,0,7], [2,2,1,1])
3