Leetcode 853. Armada Mobil

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
• Semua nilai dari positionadalah unik .
• 0 < speed[i] <= 106

1. Urutkan berdasarkan posisi mobil
2. loop melalui arr mundur dan hitung waktu untuk mencapai target
3. mari kita asumsikan mobil saat ini membutuhkan waktu t
4. jika t kurang dari waktu mobil sebelumnya maka ia akan menyusul dan bergabung dengan armada
5. selain itu ini adalah armada baru yang pertama jadi, tambahkan satu ke ans karena ini adalah armada baru.

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