48 lines
1.9 KiB
Python
48 lines
1.9 KiB
Python
class Solution(object):
|
|
def carFleet(self, target, position, speed):
|
|
"""
|
|
There are n cars going to the same destination along a one-lane road. The destination is target miles away.
|
|
|
|
You are given two integer array position and speed, both of length n, where position[i] is the position of
|
|
the ith car and speed[i] is the speed of the ith car (in miles per hour).
|
|
|
|
A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the
|
|
same speed. The faster car will slow down to match the slower car's speed. The distance between these two
|
|
cars is ignored (i.e., they are assumed to have the same position).
|
|
|
|
A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a
|
|
single car is also a car fleet.
|
|
|
|
If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.
|
|
|
|
Return the number of car fleets that will arrive at the destination.
|
|
:type target: int
|
|
:type position: List[int]
|
|
:type speed: List[int]
|
|
:rtype: int
|
|
"""
|
|
n = len(speed)
|
|
# Create velocity with position and speed
|
|
v = [(position[i], speed[i]) for i in range(n)]
|
|
v.sort()
|
|
# Get Time based on displacement(distance from target) and speed
|
|
time = [float(target - v[i][0]) / v[i][1] for i in range(n)]
|
|
|
|
curr = float('-inf')
|
|
res = 0
|
|
|
|
# Find each fastest time of arrival per fleet based on new current time
|
|
for i in range(n - 1, -1, -1):
|
|
if time[i] > curr:
|
|
print(f'curr is {curr}: time is {time[i]}')
|
|
curr = time[i]
|
|
res += 1
|
|
|
|
return res
|
|
|
|
|
|
|
|
obj = Solution()
|
|
print(obj.carFleet(12,[10,8,0,5,3],[2,4,1,1,3])) # 3
|
|
print(obj.carFleet(10,[3],[3])) # 1
|
|
print(obj.carFleet(100,[0,2,4],[4,2,1])) # 1 |