N 輛車沿著一條車道駛向位于 target 英里之外的共同目的地挚躯。
每輛車 i 以恒定的速度 speed[i] (英里/小時),從初始位置 position[i] (英里) 沿車道駛向目的地。
一輛車永遠不會超過前面的另一輛車镰吵,但它可以追上去暖呕,并與前車以相同的速度緊接著行駛。
此時场躯,我們會忽略這兩輛車之間的距離谈为,也就是說,它們被假定處于相同的位置踢关。
車隊 是一些由行駛在相同位置伞鲫、具有相同速度的車組成的非空集合。注意签舞,一輛車也可以是一個車隊秕脓。
即便一輛車在目的地才趕上了一個車隊,它們?nèi)匀粫灰曌魇峭粋€車隊儒搭。
會有多少車隊到達目的地?
示例:
輸入:target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
輸出:3
解釋:
從 10 和 8 開始的車會組成一個車隊吠架,它們在 12 處相遇。
從 0 處開始的車無法追上其它車搂鲫,所以它自己就是一個車隊傍药。
從 5 和 3 開始的車會組成一個車隊,它們在 6 處相遇魂仍。
請注意拐辽,在到達目的地之前沒有其它車會遇到這些車隊,所以答案是 3擦酌。
python3解答
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
cars = sorted(zip(position, speed))
times = [float(target - p) / s for p, s in cars]
ans = 0
while len(times) > 1:
time = times.pop()
if time < times[-1]:
ans += 1
else:
times[-1] = time
return ans + bool(times)