Assign Cookies

Q: ¿Cuál es la complejidad temporal de Assign Cookies?

Ordenar los dos arreglos cuesta O(n log n + m log m) , y el recorrido con dos punteros posterior cuesta O(n + m) , así que predominan las ordenaciones. Ordenar in situ mantiene el espacio adicional en O(1) , aparte del que utiliza la propia ordenación.

Q: ¿Por qué funciona la elección voraz para Asignar galletas?

Sea k la galleta más pequeña que satisface al niño menos glotón. Supongamos que una asignación óptima le da a ese niño otra galleta. Intercambiamos: el niño toma k y quien tenía k toma la otra galleta, que es al menos tan grande como k , así que también queda satisfecho. La cantidad no cambia, por lo que una asignación óptima siempre puede empezar con la elección voraz, y el mismo argumento se repite para los niños y las galletas restantes.

FácilVoraz Ordenación

+10

Cada niño i tiene un factor de avidez g[i]: el tamaño de galleta más pequeño que lo satisface. Cada galleta j tiene un tamaño s[j]. Un niño queda satisfecho cuando recibe una galleta cuyo tamaño es al menos igual a su factor de avidez. Cada niño recibe como máximo una galleta y cada galleta se entrega como máximo a un niño. Devuelve el mayor número de niños que puedes satisfacer.

Función

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: el factor de avidez de cada niño, el tamaño de galleta más pequeño que acepta
sinteger-array: el tamaño de cada cookie
Devuelveinteger: la mayor cantidad de niños que pueden recibir cada uno una galleta al menos tan grande como su factor de avidez

Restricciones

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Los dos arreglos pueden tener longitudes diferentes, y ninguno está ordenado.

Ejemplos

Entrada: g = [4, 2, 7]s = [3, 5, 1, 2]
Salida: 2
Explicación: Ordenados, los niños quieren 2, 4 y 7, y las galletas son 1, 2, 3 y 5. La galleta 2 alimenta al niño que quiere 2, y la galleta 5 alimenta al niño que quiere 4. No queda ninguna que alcance 7, así que la respuesta es 2.

+16 pruebas ocultas al enviar

Para ir más allá

¿Y si cada niño también tuviera la galleta más grande que aceptaría, de modo que una galleta solo encajara dentro de un rango? Entonces, ¿a qué niño que está esperando debería ir cada galleta?

Solución

La pregunta es qué galleta debería recibir cada niño. Probar todas las combinaciones hace que el número de opciones se dispare, pero una regla voraz lo resuelve: atiende primero al niño menos exigente y dale la galleta más pequeña que le sirva. Después de ordenar ambos arreglos, esa regla se convierte en un recorrido único con dos punteros.

La galleta más pequeña que le quede a cada niño

Correcto, pero no termina con las pruebas más grandes

Intuición

Empieza por los niños menos glotones y termina con los más glotones. Para cada uno, revisa todas las galletas que aún no se hayan usado y elige la más pequeña que sea lo bastante grande. Si ninguna galleta sirve, ese niño se queda con hambre. En el primer ejemplo, los niños quieren 2, 4 y 7: el niño que quiere 2 recibe la galleta 2, el que quiere 4 recibe la galleta 5, y no queda nada para el que quiere 7.

¿Por qué elegir la galleta más pequeña que sirva? Una galleta más grande puede alimentar a todos los niños a los que puede alimentar la más pequeña, y a más. Repartir la más pequeña que sirva deja las galletas más grandes para los niños más glotones que vienen después, así que nunca pierdes a un niño al que podrías haber alimentado.

El costo está en la búsqueda. Cada uno de los n niños recorre las m galletas, así que con n = m = 5000 son 25 millones de comprobaciones, demasiado para las pruebas más grandes.

Algoritmo

Ordena los factores de avidez de menor a mayor.
Mantén una marca para cada galleta que indique si está usada.
Para cada niño, recorre todas las galletas y recuerda la más pequeña que no esté usada y cuyo tamaño sea al menos igual a la avidez del niño.
Si encuentras una, márcala como usada y cuenta al niño como satisfecho.
Devuelve el recuento.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Ordena ambos y usa dos punteros

Intuición

El recorrido anterior busca una y otra vez la galleta más pequeña que encaja. Ordena también las galletas y esa búsqueda desaparece: las galletas quedan en orden creciente, así que encuentras primero la galleta más pequeña que encaja.

Recorre las galletas de menor a mayor y mantén un puntero, child, en el niño menos glotón que aún espera. Si la galleta es al menos g[child], ese niño recibe una galleta y el puntero avanza al siguiente niño. Si es más pequeña, también es más pequeña que la de todos los niños que aún esperan, ya que están ordenados, así que la galleta no sirve y sigues adelante.

En el primer ejemplo, las galletas ordenadas son 1, 2, 3, 5 y los niveles de glotonería ordenados son 2, 4, 7. La galleta 1 es demasiado pequeña para 2. La galleta 2 alimenta al niño que quiere 2. La galleta 3 es demasiado pequeña para 4. La galleta 5 alimenta al niño que quiere 4. El puntero se detiene en 2, que es la respuesta.

Cada puntero solo avanza, así que el recorrido es O(n + m) y las dos ordenaciones dominan el coste. Ordenar en el sitio no necesita arrays adicionales.

Algoritmo

Ordena g y s en orden creciente.
Establece child = 0, el niño menos exigente que todavía está esperando.
Para cada galleta, empezando por la más pequeña: si child todavía está dentro de g y la galleta es al menos g[child], suma 1 a child.
Devuelve child, el número de niños alimentados.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a emparejar en el orden equivocado o a mover el puntero equivocado.

Darle a un niño una galleta más grande de lo que necesita. Con g = [1, 2] y s = [1, 3], darle la galleta 3 al niño que quiere 1 deja con hambre al niño que quiere 2, mientras que la asignación correcta alimenta a ambos.
Avanzar el puntero del niño cuando una galleta es demasiado pequeña. El niño sigue necesitando una galleta; la que no sirve es la galleta.
Olvidar comprobar el límite del puntero del niño. Una vez que todos los niños están alimentados, no se debe intentar leer las galletas restantes más allá del final de g.
Comparar con > en lugar de ≥. Una galleta cuyo tamaño es exactamente igual al factor de avidez es suficiente.
Ordenar números como texto. En JavaScript, sort() sin un comparador coloca el 10 antes que el 9.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Assign Cookies?

Ordenar los dos arreglos cuesta O(n log n + m log m), y el recorrido con dos punteros posterior cuesta O(n + m), así que predominan las ordenaciones. Ordenar in situ mantiene el espacio adicional en O(1), aparte del que utiliza la propia ordenación.

¿Por qué funciona la elección voraz para Asignar galletas?

Sea k la galleta más pequeña que satisface al niño menos glotón. Supongamos que una asignación óptima le da a ese niño otra galleta. Intercambiamos: el niño toma k y quien tenía k toma la otra galleta, que es al menos tan grande como k, así que también queda satisfecho. La cantidad no cambia, por lo que una asignación óptima siempre puede empezar con la elección voraz, y el mismo argumento se repite para los niños y las galletas restantes.

¿Puedes empezar por el niño más glotón?

Sí. Ordena ambos arreglos y luego recórrelos empezando por la galleta más grande y el niño más glotón: si la galleta más grande que queda le sirve al niño más glotón que queda, dásela y avanza ambos punteros; si no, ninguna galleta podrá alimentar a ese niño, así que sáltatelo. Se obtiene la misma cantidad en el mismo tiempo.

¿Es Assign Cookies un problema de programación dinámica?

No. Un argumento de intercambio muestra que la elección codiciosa siempre es segura, así que ordenar y recorrer una vez es suficiente, en O(n log n + m log m). Una tabla sobre los dos arreglos ordenados, rellenada como una tabla de subsecuencia común más larga, también encuentra la respuesta, pero cuesta O(n × m) de tiempo para obtener el mismo resultado.

Python

def findContentChildren(g, s):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

g = [4, 2, 7]
s = [3, 5, 1, 2]

Esperado