Leetcode 853. Đội xe

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

Input: target = 10, position = [3], speed = [3]
Output: 1
Explanation: There is only one car, hence there is only one fleet.

Input: target = 100, position = [0,2,4], speed = [4,2,1]
Output: 1
Explanation:
The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The fleet moves at speed 2.
Then, the fleet (speed 2) and the car starting at 4 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

• n == position.length == speed.length
• 1 <= n <= 105
• 0 < target <= 106
• 0 <= position[i] < target
• Tất cả các giá trị của positionlà duy nhất .
• 0 < speed[i] <= 106

1. Phân loại dựa trên vị trí của xe
2. lặp qua mảng ngược và tính toán thời gian để đạt được mục tiêu
3. giả sử chiếc xe hiện tại mất t thời gian
4. nếu t nhỏ hơn thời gian xe trước đó thì nó sẽ đuổi kịp và gia nhập đoàn xe
5. nếu không, đây là chiếc đầu tiên của hạm đội mới, vì vậy, hãy thêm một chiếc vào ans vì đây là một hạm đội mới.

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        
        arr = [[pos, speed] for pos, speed in zip(position, speed)]
        arr.sort(key = lambda x: x[0])

        ans = 0
        prev = -1
        for pos, speed in arr[::-1]:
            time = (target - pos)/speed
            # print(pos, speed, time, prev)
            if(prev<time):
                ans += 1
                prev = time
        
        return ans