Repartir galletas
La misión
Problema
Cada niño tiene un tamaño mínimo de galleta que lo hace feliz, y cada galleta tiene un tamaño. Un niño recibe como máximo una galleta y una galleta va como máximo a un niño. Devuelve la mayor cantidad de niños que puedes hacer felices.
Ejemplos
Input: wants = [1, 2, 3], sizes = [1, 1]
Output: 1
Por qué: las dos galletas solo satisfacen al niño que quiere tamaño 1
Input: wants = [1, 2], sizes = [1, 2, 3]
Output: 2
Input: wants = [5], sizes = []
Output: 0
Por qué: caso límite: sin galletas no hay niños felices
Pistas
0 / 3
Darle la galleta más grande a quien la pida primero puede desperdiciarla en un niño al que le habría bastado una galleta pequeña. Piensa a qué niño debería ir cada galleta.
Ordena ambas listas. El niño menos exigente es el más fácil de complacer, y la galleta más pequeña que lo complace es la forma más barata de hacerlo.
Recorre las galletas de la más pequeña a la más grande con un puntero sobre los niños ordenados. Si la galleta actual alcanza para el niño menos exigente que sigue esperando, dásela y avanza el puntero; si no, la galleta es demasiado pequeña para todos los que quedan, así que sáltala.
- Tiempo objetivo
- O(n log n + m log m)
- Espacio objetivo
- O(n + m)
Solución
Después de ordenar, el niño menos exigente que sigue esperando es el que más conviene atender, y la galleta más pequeña que lo satisface es la que menos cuesta usar; un argumento de intercambio muestra que acercar cualquier asignación óptima a esta elección nunca pierde un niño feliz. Una galleta demasiado pequeña para el niño menos exigente que espera también lo es para todos los que vienen después, así que se descarta. Una pasada por las galletas con un puntero sobre los niños hace el resto. El tiempo es O(n log n + m log m) por los ordenamientos, y el espacio es O(1) aparte de ellos.
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], [])) # -> 0¿Lo que te frena es la idea y no el código? ¿Qué hace que greedy funcione? lo explica.