Distribuir biscoitos
A missão
Problema
Cada criança tem um tamanho mínimo de biscoito que a deixa feliz, e cada biscoito tem um tamanho. Uma criança recebe no máximo um biscoito, e um biscoito vai para no máximo uma criança. Retorne o maior número de crianças que você consegue deixar felizes.
Exemplos
Input: wants = [1, 2, 3], sizes = [1, 1]
Output: 1
Por quê: os dois biscoitos só satisfazem a criança que quer o tamanho 1
Input: wants = [1, 2], sizes = [1, 2, 3]
Output: 2
Input: wants = [5], sizes = []
Output: 0
Por quê: edge case: sem biscoitos, não há crianças felizes
Dicas
0 / 3
Dar o maior biscoito a quem pede primeiro pode desperdiçá-lo com uma criança que um biscoito pequeno teria satisfeito. Pense em qual criança deve receber cada biscoito.
Ordene as duas listas. A criança menos exigente é a mais fácil de agradar, e o menor biscoito que a agrada é o jeito mais barato de fazer isso.
Percorra os biscoitos do menor para o maior, com um ponteiro nas crianças ordenadas. Se o biscoito atual for grande o bastante para a criança menos exigente que ainda espera, entregue-o a ela e avance o ponteiro; caso contrário, o biscoito é pequeno demais para todas as que restam, então pule-o.
- Tempo-alvo
- O(n log n + m log m)
- Espaço-alvo
- O(n + m)
Solução
Depois de ordenar, a criança menos exigente que ainda espera é a que mais vale atender, e o menor biscoito que a satisfaz é aquele cujo uso custa menos; um argumento de troca mostra que ajustar qualquer distribuição ótima na direção dessa escolha nunca perde uma criança feliz. Um biscoito pequeno demais para a criança menos exigente que ainda espera também é pequeno demais para todas as que vêm depois dela, então ele é descartado. Uma passada pelos biscoitos, com um ponteiro nas crianças, faz o resto. O tempo é O(n log n + m log m) pelas ordenações, e o espaço é O(1) além delas.
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], [])) # -> 0Travou na ideia, e não no código? O que faz um algoritmo guloso funcionar explica isso.