Leetcode 875 Koko Eating Bananas

Soru

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Örnek 1

Input: piles = [3,6,7,11], h = 8
Output: 4

Örnek 2

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Örnek 3

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Çözüm

• Koko’nun verilen miktarda muzları belirli bir zaman dilimi içinde yiyebilmesi için gereken minimum hızı bulmanızı ister. Koko her saat başı belirli bir hızda muz yiyor ve muzları yemeye devam ettiği sürece bu hızı saat başına sabit tutuyor. Sorunun amacı, Koko’nun tüm muzları belirtilen saatler içinde yiyebilmesi için gerekli minimum yeme hızını belirlemek.
• Girdi: Bir tam sayılar dizisi piles (her öğe bir muz yığınının boyutunu temsil eder) ve bir tam sayı H (Koko’nun muzları yemesi gereken maksimum saat sayısı).
• Çıktı: Koko’nun tüm muzları H saat içinde yiyebilmesi için gereken minimum hız.
• Bu problem ikili arama yöntemi kullanılarak çözülebilir. Hız aralığını daraltarak, Koko’nun tüm muzları belirlenen süre içinde yiyip yiyemeyeceğini kontrol edersiniz. Minimum hızı ve maksimum hızı belirlemek için muz yığınlarının maksimum değeri kullanılır ve bu hızlar arasında ikili arama yapılır.
• Çalışma Mekanizması:
• Hız Aralığının Belirlenmesi: Minimum hız 1, maksimum hız ise piles dizisinin maksimum değeri olarak belirlenir.
• İkili Arama: Minimum ve maksimum hız arasında ikili arama yapılır. Her adımda, orta değer (mid) kullanılarak canFinish fonksiyonu çağrılır. Bu fonksiyon, belirli bir hızda tüm muzların yenebilip yenemeyeceğini kontrol eder.
• Sonuç: İkili arama tamamlandığında, left değeri, Koko’nun tüm muzları belirlenen süre içinde yiyebilmesi için gerekli olan minimum hızı gösterir.

Code

class Solution:
    def minEatingSpeed(self, piles, H):
        def canFinish(k):
            time = 0
            for pile in piles:
                time += (pile - 1) // k + 1  # Her yığını k hızında yemek için gereken saat
            return time <= H

        left, right = 1, max(piles)  # Hız aralığı 1 ile en büyük yığın arasında
        while left < right:
            mid = (left + right) // 2
            if canFinish(mid):
                right = mid  # Daha düşük bir hızda deneyin
            else:
                left = mid + 1  # Hızı arttırın

        return left

        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(N log M), burada N piles dizisinin uzunluğu ve M maksimum muz yığını boyutudur. Her canFinish çağrısı O(N) süre alır ve ikili arama O(log M) süre alır.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra bir alan kullanılmaz; tüm işlemler girdi üzerinde yerinde gerçekleştirilir.