Book Allocation Problem

Q: ¿Es el problema de asignación de libros lo mismo que el de dividir un arreglo para minimizar la suma máxima?

Sí. Ambos dividen un arreglo en una cantidad fija de bloques contiguos no vacíos y minimizan la suma del bloque más grande, y la misma búsqueda binaria con la misma comprobación voraz resuelve ambos. La versión del libro añade el caso -1 .

Q: ¿Cuál es la complejidad temporal del problema de asignación de libros?

Tiempo O(n log S) y espacio adicional O(1) , donde n es el número de libros y S el total de páginas. Cada límite probado requiere recorrer los libros una vez, y la búsqueda prueba aproximadamente log2 S límites: 29 en una estantería de 5 × 10^8 páginas.

Q: ¿Cuándo es imposible asignar los libros?

Solo cuando hay más estudiantes que libros, ya que cada estudiante necesita al menos un libro. Si hay suficientes libros, cualquier bloque de dos o más libros puede darle el último libro a un estudiante que no tenga ninguno, hasta que todos tengan uno.

MedioBúsqueda binaria Voraz

+10

Un estante contiene libros en un orden fijo, y pages[i] es el número de páginas del libro i. Reparte los libros entre students estudiantes: cada estudiante recibe un tramo continuo de libros contiguos, al menos un libro cada uno, y cada libro se asigna exactamente a un estudiante. La carga de un estudiante es el número total de páginas que recibe.

Devuelve el menor valor posible de la carga más pesada. Si hay más estudiantes que libros, devuelve -1.

Función

allocateBooks(pages: integer-array, students: integer) → integer

pagesinteger-array: la cantidad de páginas de cada libro, en el orden de los estantes
studentsinteger: el número de estudiantes que comparten los libros
Devuelveinteger: la carga más pesada posible más pequeña, o -1 cuando hay más estudiantes que libros

Restricciones

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Devuelve -1 cuando students > pages.length.

Ejemplos

Entrada: pages = [25, 40, 15, 30, 50]students = 3
Salida: 65
Explicación: Reparte [25, 40], [15, 30] y [50]: las cargas son 65, 45 y 50. Un límite de 64 no funciona: el reparto da [25], [40, 15], [30], [50], cuatro estudiantes.

Entrada: pages = [10, 20]students = 3
Salida: -1
Explicación: Dos libros no pueden dar un libro a cada uno de los tres estudiantes, así que la respuesta es -1.

Para ir más allá

Demuestra que la cuota promedio, redondeada hacia arriba, más el libro más grueso siempre es un límite válido. ¿Cuántas comprobaciones ahorra ese límite superior en un estante de libros delgados?

Pistas

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

0 de 3 abiertas

Solución

Hay demasiadas formas de dividir los libros del estante, pero probar un límite por página es barato: reparte los libros en el orden del estante, pasa al siguiente estudiante cuando un libro supere el límite y cuenta a los estudiantes. Un límite más alto nunca requiere más estudiantes, así que los límites que funcionan forman un intervalo, y la búsqueda binaria encuentra dónde empieza.

Aumenta el límite de páginas de una en una

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

Intuición

Empieza en L = max(pages), ya que alguien lleva el libro más grueso, y aumenta L una página cada vez hasta que el recuento voraz quepa en students. Todos los límites inferiores fallaron, así que el primero que funciona es la respuesta. En el primer ejemplo, todos los límites de 50 a 64 necesitan cuatro estudiantes y 65 necesita tres: 16 comprobaciones.

La respuesta puede ser toda la estantería: un estudiante y 5000 libros de 10^5 páginas significan unos 5 × 10^8 límites, cada uno de los cuales requiere recorrer los 5000 libros. En la columna de tiempo, A es la respuesta y m el libro más grueso.

Algoritmo

Si students > pages.length, devuelve -1.
Escribe el recuento voraz para un límite L: empieza con un estudiante y una carga de 0; cuando load + pages[i] > L, añade un estudiante y establece la carga en pages[i]; de lo contrario, añade el libro a la carga.
Establece L en el libro más grueso.
Mientras el recuento para L sea mayor que students, suma 1 a L.
Devuelve L.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    limit = max(pages)  # the thickest book has to fit somewhere
    while studentsNeeded(pages, limit) > students:
        limit += 1
    return limit

Búsqueda binaria en el límite de la página

Intuición

El recuento voraz es la menor cantidad de estudiantes que puede usar cualquier reparto con L. Si se compara estudiante por estudiante con cualquier otro reparto, cada estudiante del reparto voraz se detiene solo cuando el siguiente libro no cabe, por lo que termina al menos igual de avanzado en el estante. Está bien tener menos estudiantes de los que tienes: un estudiante que sostiene dos libros puede pasarle uno a un estudiante que no tiene ninguno, y ninguna carga aumenta.

Así que L funciona exactamente cuando el recuento voraz es como máximo students. Todo lo que funciona con L también funciona con L+1, por lo que la búsqueda binaria encuentra el primer límite que funciona.

El rango comienza en el mayor valor entre max(pages) y el reparto promedio, total / students redondeado hacia arriba, ya que la carga más pesada es al menos igual a ambos. El límite superior es total. En el primer ejemplo, el rango va de 54 a 160, y la búsqueda prueba 107, 80, 67, 60, 64, 66 y 65.

Algoritmo

Si students > pages.length, devuelve -1.
Suma total y encuentra el libro más grueso. Establece lo con el valor mayor entre el libro más grueso y (total + students - 1) / students, y hi = total.
Mientras lo < hi, calcula mid = lo + (hi - lo) / 2.
Ejecuta el recuento voraz para mid. Si es como máximo students, establece hi = mid; de lo contrario, establece lo = mid + 1.
Devuelve lo.

def studentsNeeded(pages, limit):
    count, load = 1, 0  # the first student starts with no pages
    for p in pages:
        if load + p > limit:
            count += 1  # this book opens the next student's block
            load = p
        else:
            load += p
    return count


def allocateBooks(pages, students):
    if students > len(pages):
        return -1  # someone would get no book
    total = sum(pages)
    # no limit can be below the thickest book or below the average share
    lo = max(max(pages), (total + students - 1) // students)
    hi = total  # one student could carry the whole shelf
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if studentsNeeded(pages, mid) <= students:
            hi = mid  # mid is enough, so the answer is mid or lower
        else:
            lo = mid + 1  # mid needs too many students
    return lo

Errores comunes y casos límite

Omitir la comprobación de -1. Para [10, 20] y 3 estudiantes, el recuento voraz con un límite de 20 es 2, así que la búsqueda devuelve 20.
Empezar el rango únicamente en la cuota promedio. Para [1, 9] y 2 estudiantes, el promedio es 5, y con ese límite el algoritmo voraz asigna el libro de 9 páginas por separado, cuenta 2 y devuelve 5.
Comprobar si es exactamente igual a students. Para [5, 5, 5, 5, 5, 5] y 4 estudiantes, la respuesta es 10, donde el recuento voraz es 3.
Ordenar los libros. [10, 1, 1, 10] con 2 estudiantes da 11, pero ordenado como [1, 1, 10, 10] da 12.

Preguntas frecuentes3

¿Es el problema de asignación de libros lo mismo que el de dividir un arreglo para minimizar la suma máxima?

Sí. Ambos dividen un arreglo en una cantidad fija de bloques contiguos no vacíos y minimizan la suma del bloque más grande, y la misma búsqueda binaria con la misma comprobación voraz resuelve ambos. La versión del libro añade el caso -1.

¿Cuál es la complejidad temporal del problema de asignación de libros?

Tiempo O(n log S) y espacio adicional O(1), donde n es el número de libros y S el total de páginas. Cada límite probado requiere recorrer los libros una vez, y la búsqueda prueba aproximadamente log2 S límites: 29 en una estantería de 5 × 10^8 páginas.

¿Cuándo es imposible asignar los libros?

Solo cuando hay más estudiantes que libros, ya que cada estudiante necesita al menos un libro. Si hay suficientes libros, cualquier bloque de dos o más libros puede darle el último libro a un estudiante que no tenga ninguno, hasta que todos tengan uno.

def allocateBooks(pages, students):
    # Escribe el código aquí

Prueba #1

Prueba #2

Prueba #3

Argumentos

pages = [25, 40, 15, 30, 50]
students = 3

Salida Esperada