Leetcode 853 Car Fleet

Soru

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer array position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour.

A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car.

A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet.

If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet.

Return the number of car fleets that will arrive at the destination.

Örnek 1

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 fleet forms at target.
The car starting at 0 (speed 1) 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.

Örnek 2

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation:

There is only one car, hence there is only one fleet.

Örnek 3

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 car starting at 4 (speed 1) travels to 5.
Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Çözüm

• Bir hedefe doğru ilerleyen bir dizi arabanın ne kadarlık bir filo oluşturabileceğini hesaplamanızı isteyen bir problem. Arabalar farklı hızlarda hareket ediyor ve eğer bir araba daha yavaş bir arabayı yakalarsa, bu iki araba birlikte hareket eder ve bir filo oluştururlar. Sorun, her bir arabanın başlangıç pozisyonunu, hızını ve hedefe olan mesafeyi içerir ve sizden arabaların hedefe varmadan önce kaç farklı filo oluşturacağını hesaplamanızı ister.
• Girdi: target: Hedefin pozisyonu. position: Arabaların başlangıç pozisyonlarını içeren bir tam sayı dizisi. speed: Arabaların hızlarını içeren bir tam sayı dizisi.
• Çıktı: Hedefe varmadan önce oluşan toplam filo sayısı.
• Bu problem, arabaları başlangıç pozisyonlarına göre sıralayarak ve her bir arabanın hedefe ulaşma süresini hesaplayarak çözülebilir. Arabaları geriden ileriye doğru incelerken, eğer bir araba önceki arabayı yakalayacak kadar hızlı değilse, bu durumda yeni bir filo oluşur.
• Çalışma Mekanizması:
• Arabaları Sırala: Arabaları pozisyonlarına göre sırala, böylece en arkadakinden başlayarak ileriye doğru işlem yapabilirsin.
• Ulaşma Sürelerini Hesapla: Her bir araba için hedefe ulaşma süresini hesapla.
• Filoları Say: En arkadaki arabadan başlayarak, eğer bir araba öncekine yetişemiyorsa (yani süresi daha uzunsa) yeni bir filo sayılır ve bu arabanın süresi esas alınır.
• Sonuç Dönüşü: Filo sayısını döndür.
• Bu çözüm, verilen hedefe doğru ilerlerken arabaların oluşturduğu filo sayısını verimli ve etkili bir şekilde hesaplar. Her bir arabanın diğerlerine göre ne zaman bağımsız hareket etmeye başlayacağını süre hesaplamaları ile belirler.

Code

   class Solution:
    def carFleet(self, target, position, speed):
        # Pozisyon ve hızları birlikte ele almak için tuple listesi oluştur
        cars = sorted(zip(position, speed))
        
        # Her arabanın hedefe ulaşma süresini hesapla ve bir listeye kaydet
        times = [(target - p) / s for p, s in cars]
        
        fleets = 0
        while times:
            lead_time = times.pop()  # En arkadaki arabanın süresini al
            fleets += 1
            # Sonraki arabaların süresi, bu süreden daha büyükse yeni filo
            while times and times[-1] <= lead_time:
                times.pop()
        
        return fleets

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n log n), burada n araba sayısıdır. Arabaları sıralamak için n log n zaman gerekir ve sonrasında n kadar süre hesaplaması ve karşılaştırması yapılır.
• Space complexity (Alan Karmaşıklığı) : O(n), arabaların ve sürelerinin saklanması için gereken alan.