N 輛車沿著一條車道駛向位于 target 英里之外的共同目的地蜂桶。
每輛車 i 以恒定的速度 speed[i] （英里/小時(shí)），從初始位置 position[i] （英里） 沿車道駛向目的地才沧。
一輛車永遠(yuǎn)不會(huì)超過前面的另一輛車，但它可以追上去注竿，并與前車以相同的速度緊接著行駛辰妙。
此時(shí)，我們會(huì)忽略這兩輛車之間的距離仆抵，也就是說跟继，它們被假定處于相同的位置种冬。
車隊(duì) 是一些由行駛在相同位置、具有相同速度的車組成的非空集合舔糖。注意娱两，一輛車也可以是一個(gè)車隊(duì)。
即便一輛車在目的地才趕上了一個(gè)車隊(duì)金吗，它們?nèi)匀粫?huì)被視作是同一個(gè)車隊(duì)十兢。
會(huì)有多少車隊(duì)到達(dá)目的地?
示例：
輸入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
輸出：3
解釋：
從 10 和 8 開始的車會(huì)組成一個(gè)車隊(duì)，它們?cè)?12 處相遇摇庙。
從 0 處開始的車無法追上其它車旱物，所以它自己就是一個(gè)車隊(duì)。
從 5 和 3 開始的車會(huì)組成一個(gè)車隊(duì)卫袒，它們?cè)?6 處相遇宵呛。
請(qǐng)注意，在到達(dá)目的地之前沒有其它車會(huì)遇到這些車隊(duì)夕凝，所以答案是 3宝穗。
來源鏈接：https://leetcode-cn.com/problems/car-fleet
由題意可知,后車最多和前車并行前進(jìn),則第一個(gè)到達(dá)的必定是最近的車.
所以解題流程是這樣的，先算出每輛車輛到達(dá)目的地所需的時(shí)間,然后按照距目的地的距離排序.
遍歷排序結(jié)果,取出第一輛車(距目的地最近的車),判斷后車到達(dá)時(shí)間是否比前車小:
是,則表示其會(huì)追上前車,二者視為一個(gè)車隊(duì).
否,則刷新最慢到達(dá)時(shí)間,此后車視為新車隊(duì)的隊(duì)頭.
遍歷完成,返回到達(dá)時(shí)間的變化數(shù),則是車隊(duì)數(shù)量.
以下是go語言的實(shí)現(xiàn)版:
type node struct {
pos int
times float64
}
func carFleet(target int, position []int, speed []int) int {
node := make([]node, len(position))
if len(position) == 0 {
return 0
}
for i, _ := range position {
node[i].pos = position[i]
node[i].times = float64(target-position[i]) / float64(speed[i])
}
sort.Slice(node, func(i, j int) bool {
return node[i].pos > node[j].pos
})
sign := node[0].times
count := 1
for _, time := range node {
if time.times > sign {
count++
sign = time.times
}
}
return count
}
