Koko Eating Bananas

Q: ¿Cuál es la complejidad temporal de Koko Eating Bananas?

La búsqueda binaria se ejecuta en O(n log m) tiempo, donde n es el número de montones y m el montón más grande: aproximadamente log2(m) comprobaciones, 30 cuando m = 10^9 , cada una leyendo todos los montones una vez. El espacio adicional es O(1) .

Q: ¿Cuáles son los límites inferior y superior de la velocidad?

El límite superior es la pila más grande: allí cada pila tarda una hora, lo que siempre cabe. El límite inferior es 1, y puedes aumentarlo hasta el número total de bananas dividido entre h , redondeado hacia arriba, porque Koko come como máximo k bananas por hora.

Q: ¿Cómo se divide y se redondea hacia arriba con números enteros?

Usa (p + k-1) / k con división entera. Sumar k-1 hace que cualquier resto pase al siguiente múltiplo de k , mientras que un múltiplo exacto se queda igual: 10 a velocidad 4 da 13 / 4 = 3 , y 8 da 11 / 4 = 2 . No se necesitan números de punto flotante.

MedioBúsqueda binaria

+10

Koko tiene n montones de plátanos, con piles[i] plátanos en el montón i, y h horas. Elige una velocidad de consumo k, un número entero de plátanos por hora, y la mantiene. Cada hora come k plátanos de un montón; si a ese montón le quedan menos de k, lo termina y descansa hasta que acabe la hora. Devuelve el valor más pequeño de k que le permita terminar todos los montones en un máximo de h horas.

Función

minEatingSpeed(piles: integer-array, h: integer) → integer

pilesinteger-array: el número de bananas en cada pila
hinteger: la cantidad de horas que tiene Koko
Devuelveinteger: la menor velocidad de consumo, en bananas por hora, que termina cada pila en un máximo de h horas

Restricciones

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, por lo que siempre existe una respuesta.

Ejemplos

Entrada: piles = [4, 10, 7, 3]h = 6
Salida: 5
Explicación: A velocidad 5, las pilas 4, 10, 7 y 3 tardan 1, 2, 2 y 1 horas: 6 en total, lo cual encaja. A velocidad 4 tardan 1, 3, 2 y 1, que suman 7.

Para ir más allá

Problema gemelo: Koko se come montones enteros en orden, como máximo k plátanos al día, en un plazo de d días. ¿Cuál es el menor valor de k y qué cambia en tu búsqueda?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La respuesta es una velocidad, no una posición en el arreglo, y eso oculta una búsqueda binaria. Comprobar una velocidad requiere recorrer las pilas una vez, y si la velocidad k termina a tiempo, todas las velocidades más rápidas también lo hacen. Así que busca las velocidades mediante búsqueda binaria, desde 1 hasta la pila más grande: unas 30 comprobaciones en lugar de hasta mil millones.

Prueba todas las velocidades desde 1 en adelante

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

Intuición

Koko nunca pasa a otra pila dentro de una hora, así que una pila de p bananas requiere p / k horas redondeadas hacia arriba: a velocidad 4, 10 bananas requieren 3 horas. Prueba velocidades de 1, 2, 3 y así sucesivamente, y devuelve la primera cuyo total quepa en h. Es la menor porque todas las velocidades más lentas fallaron, y el bucle se detiene al llegar a la velocidad de la pila más grande, con la que cada pila requiere una hora.

Si m es la pila más grande, se realizan hasta m comprobaciones de n pilas: unos 5 × 10^12 pasos para 5000 pilas de casi 10^9 y h = 5000.

Algoritmo

Establece speed = 1.
Cuenta las horas a esta velocidad: para cada pila, suma (pile + speed-1) / speed, usando un total de 64 bits.
Si el total es como máximo h, devuelve speed.
De lo contrario, suma 1 a speed y vuelve a contar.

def minEatingSpeed(piles, h):
    speed = 1
    while True:
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # a started pile costs a whole hour
        if hours <= h:
            return speed
        speed += 1

Búsqueda binaria de velocidad

Intuición

A medida que aumenta la velocidad, cada montón tarda la misma cantidad de horas o menos, así que las respuestas a «¿esta velocidad termina a tiempo?» son no, no, no y después sí, a partir de la respuesta. La búsqueda binaria encuentra ese primer sí.

Mantén un rango de lo a hi que siempre contenga la respuesta, empezando en 1 y en el montón más grande, cuya velocidad tarda una hora por montón y, por tanto, cumple con el tiempo. Si la velocidad intermedia mid cumple, la respuesta es mid o una velocidad menor, así que establece hi = mid. Si no, todas las velocidades menores también fallan, así que establece lo = mid + 1. Cuando lo llega a hi, esa es la respuesta.

En el primer ejemplo, el rango empieza de 1 a 10. La velocidad 5 cumple, así que el rango pasa a ser de 1 a 5; la velocidad 3 tarda 10 horas, así que el rango pasa a ser de 4 a 5; la velocidad 4 tarda 7, así que el rango pasa a ser de 5 a 5.

Algoritmo

Establece lo = 1 y hi en la pila más grande.
Mientras lo < hi, toma mid = lo + (hi - lo) / 2.
Cuenta las horas a velocidad mid: suma (pile + mid-1) / mid por cada pila, en un total de 64 bits.
Si el total es como máximo h, establece hi = mid; de lo contrario, establece lo = mid + 1.
Devuelve lo.

def minEatingSpeed(piles, h):
    lo, hi = 1, max(piles)  # the largest pile always works: one hour per pile
    while lo < hi:
        mid = lo + (hi - lo) // 2
        hours = 0
        for pile in piles:
            hours += (pile + mid - 1) // mid
        if hours <= h:
            hi = mid  # mid works, so the answer is mid or slower
        else:
            lo = mid + 1  # mid is too slow, so the answer is faster
    return lo

Errores comunes y casos límite

Desbordamiento del recuento de horas. A velocidad 1, 5000 montones de 10^9 plátanos requieren 5 × 10^12 horas, superando el límite de 32 bits, y un total desbordado puede hacer que una velocidad lenta pase. Cuenta con 64 bits o detente cuando el total supere h.
Redondear hacia abajo. 10 / 4 da 2, pero ese montón requiere 3 horas.
Empezar el rango en 0. Entonces mid puede ser 0 y el recuento se divide por cero.
Establecer hi = mid - 1 cuando mid sea suficiente. Eso puede descartar la respuesta.
Empezar hi por debajo del montón más grande. Cuando h es igual al número de montones, todas las velocidades inferiores fallan y la búsqueda devuelve una de ellas.

Preguntas frecuentes3

¿Cuál es la complejidad temporal de Koko Eating Bananas?

La búsqueda binaria se ejecuta en O(n log m) tiempo, donde n es el número de montones y m el montón más grande: aproximadamente log2(m) comprobaciones, 30 cuando m = 10^9, cada una leyendo todos los montones una vez. El espacio adicional es O(1).

¿Cuáles son los límites inferior y superior de la velocidad?

El límite superior es la pila más grande: allí cada pila tarda una hora, lo que siempre cabe. El límite inferior es 1, y puedes aumentarlo hasta el número total de bananas dividido entre h, redondeado hacia arriba, porque Koko come como máximo k bananas por hora.

¿Cómo se divide y se redondea hacia arriba con números enteros?

Usa (p + k-1) / k con división entera. Sumar k-1 hace que cualquier resto pase al siguiente múltiplo de k, mientras que un múltiplo exacto se queda igual: 10 a velocidad 4 da 13 / 4 = 3, y 8 da 11 / 4 = 2. No se necesitan números de punto flotante.

def minEatingSpeed(piles, h):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

piles = [4, 10, 7, 3]
h = 6

Salida Esperada