题目描述：

LeetCode 853. Car Fleet

N cars are going to the same destination along a one lane road.  The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

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 distance between these two cars is ignored - 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.

How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

1. 0 <= N <= 10 ^ 4
2. 0 < target <= 10 ^ 6
3. 0 < speed[i] <= 10 ^ 6
4. 0 <= position[i] < target
5. All initial positions are different.

题目大意：

x轴有若干车辆，坐标为整数数组position，每个车辆的速度为speed。

当后车追上前车时，两车为一组，以前车的速度继续前进；多车的情况以此类推。

求车辆在到达target时，会有多少组。

解题思路：

排序（Sort）

按照起点倒序，到达目标的预计时间（不考虑多车相遇）为正序对车辆进行排序，记为status。

初始令时间ctime为0，计数器ans为0

遍历status，当时间t > ctime时（表示后车不会与前车相遇）：更新ctime，并令ans+1

Python代码：

class Solution(object):
    def carFleet(self, target, position, speed):
        """
        :type target: int
        :type position: List[int]
        :type speed: List[int]
        :rtype: int
        """
        status = [(-p, float(target - p) / s) for p, s in zip(position, speed)]
        status.sort()
        ctime = 0
        ans = 0
        for p, t in status:
            if t > ctime:
                ans += 1
                ctime = t
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/06/17/leetcode-car-fleet/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码