853. 車隊
標(biāo)簽: 貪心算法
N 輛車沿著一條車道駛向位于 target 英里之外的共同目的地获洲。
每輛車 i 以恒定的速度 speed[i] （英里/小時）虏冻，從初始位置 position[i] （英里） 沿車道駛向目的地瞧剖。
一輛車永遠(yuǎn)不會超過前面的另一輛車，但它可以追上去存谎，并與前車以相同的速度緊接著行駛返顺。
此時，我們會忽略這兩輛車之間的距離站绪，也就是說遭铺，它們被假定處于相同的位置。
車隊 是一些由行駛在相同位置恢准、具有相同速度的車組成的非空集合魂挂。注意，一輛車也可以是一個車隊馁筐。
即便一輛車在目的地才趕上了一個車隊锰蓬，它們?nèi)匀粫灰曌魇峭粋€車隊。
會有多少車隊到達(dá)目的地?
思路
先過濾出有用的信息并處理, 觀察題目后我們可以知道:
問題: 會有多少車隊到達(dá)目的地?
限制條件: 一輛車永遠(yuǎn)不會超過前面的另一輛車, 即初始位置(position)是結(jié)果的主要影響因素
速度是另一個影響因素
-
從已知條件出發(fā):
- 先對根據(jù)初始位置對每個車的信息進行排序
- 計算最接近目的地的一輛車的到達(dá)時間, 與它后方的一輛車進行比較, 如果后一輛車的到達(dá)時間<= 當(dāng)前車的到達(dá)時間, 則因為限制條件的存在, 它們會同時到達(dá)
- 反之, 則它們不同時到達(dá), 后一輛車形成新的車隊, 為同一車隊
- 邊界條件: 當(dāng)N=0時, 會有0個車隊到達(dá); N = 1時, 1個車隊到達(dá)
解法
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
lst = sorted(zip(position, speed))
times = [(target-p)/s for p, s in lst ]
ans = 0
while len(times) > 1:
lead = times.pop()
if lead < times[-1]:
ans += 1
else:
times[-1] = lead
# 當(dāng)times = 1時,不進入循環(huán), 最后一隊車沒有可比較的對象, 沒有+1, 所以此處需要+1
# 當(dāng)time = 0時, 不進入循環(huán), 沒有車隊, 所以此處為0
# 合并上述兩項, 所以采用如下寫法
return ans + bool(times)
