Kurabiye dağıt
Görev tanımı
Problem
Her çocuğu mutlu edecek en küçük bir kurabiye boyutu var ve her kurabiyenin bir boyutu var. Bir çocuk en fazla bir kurabiye alır, bir kurabiye de en fazla bir çocuğa gider. Mutlu edebileceğin en büyük çocuk sayısını döndür.
Örnekler
Input: wants = [1, 2, 3], sizes = [1, 1]
Output: 1
Neden: iki kurabiye de yalnız 1 boyutunu isteyen çocuğu tatmin ediyor
Input: wants = [1, 2], sizes = [1, 2, 3]
Output: 2
Input: wants = [5], sizes = []
Output: 0
Neden: edge case: kurabiye yoksa mutlu çocuk da yok
İpuçları
0 / 3
En büyük kurabiyeyi ilk isteyene vermek, onu küçük bir kurabiyenin tatmin edeceği bir çocuğa harcayabilir. Her kurabiyenin hangi çocuğa gitmesi gerektiğini düşün.
İki listeyi de sırala. En az talepkâr çocuğu memnun etmek en kolayıdır, onu memnun eden en küçük kurabiye de bunu yapmanın en ucuz yoludur.
Sıralı çocuklar üzerinde bir pointer'la kurabiyeleri en küçükten en büyüğe dolaş. Mevcut kurabiye hâlâ bekleyen en az talepkâr çocuk için yeterince büyükse onu ver ve pointer'ı ilerlet; değilse kurabiye kalan herkes için çok küçüktür, atla.
- Hedef zaman
- O(n log n + m log m)
- Hedef alan
- O(n + m)
Çözüm
Sıraladıktan sonra bekleyen en az talepkâr çocuk hizmet edilmeye en değer olandır, onu tatmin eden en küçük kurabiye de kullanımı en az maliyetli olandır; bir exchange argument, herhangi bir optimal atamayı bu seçime doğru değiştirmenin asla mutlu bir çocuk kaybettirmediğini gösterir. Bekleyen en az talepkâr çocuk için çok küçük olan bir kurabiye ondan sonraki herkes için de çok küçüktür, bu yüzden atılır. Geri kalanını kurabiyeler üzerinde tek bir geçiş ve çocuklara bakan bir pointer yapar. Sıralamalar için zaman O(n log n + m log m), onlar dışında alan O(1).
def happy_children(wants, sizes):
wants, sizes = sorted(wants), sorted(sizes)
child = 0 # least demanding child still waiting
for s in sizes: # smallest cookie first
if child < len(wants) and s >= wants[child]:
child += 1 # this cookie is enough, hand it over
return child
print(happy_children([1, 2, 3], [1, 1])) # -> 1
print(happy_children([1, 2], [1, 2, 3])) # -> 2
print(happy_children([5], [])) # -> 0Kodda değil de fikirde mi takıldın? Greedy ne zaman işe yarar bunu anlatıyor.