题目

https://leetcode.com/problems/car-fleet/

题解

看了答案

分析

我们首先对这些车辆按照它们的起始位置降序排序，并且用 (target - position) / speed 计算出每辆车在不受其余车的影响时，行驶到终点需要的时间。对于相邻的两辆车 S 和 F，F 的起始位置大于 S，如果 S 行驶到终点需要的时间小于等于 F，那么 S 一定会在终点前追上 F 并形成车队。这是因为在追上 F 之前，S 的行驶速度并不会减小，而 F 却有可能因为追上前面的车辆而速度减小，因此 S 总能在终点前追上 F。

算法

将车辆按照起始位置降序排序后，我们顺序扫描这些车辆。如果相邻的两辆车，前者比后者行驶到终点需要的时间短，那么后者永远追不上前者，即从后者开始的若干辆车辆会组成一个新的车队；如果前者不比后者行驶到终点需要的时间短，那么后者可以在终点前追上前者，并和前者形成车队。此时我们将后者到达终点的时间置为前者到达终点的时间。

代码

最近转 golang 了…

type Car struct {
	pos  int
	time float32
}

func carFleet(target int, position []int, speed []int) int {
	n := len(position)
	cars := make([]Car, n)
	for i := 0; i < n; i++ {
		cars[i].pos = position[i]
		cars[i].time = float32(target-position[i]) / float32(speed[i])
	}
	// sort by time
	sort.Slice(cars, func(i, j int) bool {
		return cars[i].pos > cars[j].pos
	})
	fmt.Println(cars)

	// 离得近、所需时间长 和 离的远、所需时间短 在一个车队
	result := 1
	preTime := cars[0].time
	for _, car := range cars {
		if car.time > preTime {
			result++
			preTime = car.time
		}
	}
	return result
}