Leetcode 853. ขบวนรถ

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
• ค่าทั้งหมดของpositionจะไม่ซ้ำกัน
• 0 < speed[i] <= 106

1. จัดเรียงตามตำแหน่งของรถ
2. วนซ้ำ arr ย้อนหลังและคำนวณเวลาที่จะถึงเป้าหมาย
3. สมมติว่ารถคันปัจจุบันใช้เวลา t
4. ถ้า t น้อยกว่าเวลารถก่อนหน้าที่จะตามทันและเข้าร่วมกองเรือ
5. มิฉะนั้นจะเป็นลำแรกของกองเรือใหม่ ดังนั้นเพิ่มหนึ่งลำในansเนื่องจากเป็นกองเรือใหม่

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