Book Allocation Problem

Q: Le problème d’allocation de livres est-il identique au problème de la plus grande somme d’un tableau partagé ?

Oui. Les deux découpent un tableau en un nombre fixe de blocs contigus non vides et minimisent la somme du bloc le plus grand, et la même recherche binaire avec la même vérification gloutonne résout les deux problèmes. La version du livre ajoute le cas -1 .

Q: Quelle est la complexité temporelle du problème d’allocation des livres ?

Un temps de O(n log S) et un espace supplémentaire de O(1) , où n est le nombre de livres et S le nombre total de pages. Chaque limite testée nécessite un parcours des livres, et la recherche teste environ log2 S limites : 29 pour une étagère de 5 × 10^8 pages.

Q: Quand est-il impossible de répartir les livres ?

Uniquement lorsqu’il y a plus d’élèves que de livres, puisque chaque élève a besoin d’au moins un livre. Avec suffisamment de livres, tout bloc de deux livres ou plus peut donner son dernier livre à un élève qui n’en a aucun, jusqu’à ce que chacun en ait un.

MoyenRecherche binaire Glouton

+10

Une étagère contient des livres dans un ordre fixe, et pages[i] est le nombre de pages du livre i. Répartis les livres entre students étudiants : chaque étudiant reçoit un bloc continu de livres voisins, au moins un livre chacun, et chaque livre est attribué à exactement un étudiant. La charge d’un étudiant correspond au nombre total de pages qu’il reçoit.

Renvoie la plus petite valeur possible de la charge la plus élevée. S’il y a plus d’étudiants que de livres, renvoie -1.

Fonction

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

pagesinteger-array: le nombre de pages de chaque livre, dans l’ordre sur l’étagère
studentsinteger: le nombre d’élèves qui se partagent les livres
Renvoieinteger: la charge maximale minimale possible, ou -1 lorsqu’il y a plus d’étudiants que de livres

Contraintes

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Renvoyez -1 lorsque students > pages.length.

Exemples

Entrée: pages = [25, 40, 15, 30, 50]students = 3
Sortie: 65
Explication: Distribue [25, 40], [15, 30] et [50] : les charges sont de 65, 45 et 50. Une limite de 64 ne convient pas : la distribution donne [25], [40, 15], [30], [50], soit quatre élèves.

Entrée: pages = [10, 20]students = 3
Sortie: -1
Explication: Deux livres ne peuvent pas donner un livre chacun à trois élèves, donc la réponse est -1.

Pour aller plus loin

Prouvez que la part moyenne, arrondie à l’entier supérieur, à laquelle on ajoute le livre le plus épais, constitue toujours une borne valide. Combien de vérifications cette borne supérieure permet-elle d’économiser pour une étagère de livres minces ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Il y a trop de façons de découper l’étagère, mais tester une limite par page coûte peu : distribuez les livres dans l’ordre de l’étagère, passez à l’étudiant suivant lorsqu’un livre dépasserait la limite, puis comptez les étudiants. Une limite plus élevée ne nécessite jamais davantage d’étudiants, donc les limites qui fonctionnent forment une suite, et la recherche binaire trouve où elle commence.

Augmentez la limite de pages d’une page à la fois

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Commencez à L = max(pages), puisque quelqu’un porte le livre le plus épais, et augmentez L d’une page à la fois jusqu’à ce que le nombre calculé par l’algorithme glouton tienne dans students. Toutes les limites inférieures ont échoué, donc la première qui convient est la réponse. Dans le premier exemple, chaque limite de 50 à 64 nécessite quatre étudiants, et 65 en nécessite trois : 16 vérifications.

La réponse peut être toute l’étagère : un étudiant et 5000 livres de 10^5 pages signifient environ 5 × 10^8 limites, chacune nécessitant un parcours des 5000 livres. Dans la colonne du temps, A est la réponse et m le livre le plus épais.

Algorithme

Si students > pages.length, renvoie -1.
Écris le décompte glouton pour une limite L : commence avec un étudiant et une charge de 0 ; lorsque load + pages[i] > L, ajoute un étudiant et définis la charge à pages[i], sinon ajoute le livre à la charge.
Définis L comme le nombre de pages du livre le plus épais.
Tant que le décompte pour L est supérieur à students, ajoute 1 à L.
Renvoie 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

Recherche binaire sur la limite de la page

Intuition

Le nombre glouton est le nombre minimum d’étudiants nécessaires pour toute répartition avec une limite de L. Comparé élève par élève à toute autre répartition, chaque élève de la répartition gloutonne s’arrête uniquement lorsque le livre suivant ne tient pas, et atteint donc au moins la même position sur l’étagère. Avoir moins d’étudiants que prévu ne pose pas de problème : un élève qui tient deux livres peut en passer un à un élève qui n’en a aucun, sans qu’aucune charge n’augmente.

La limite L convient donc exactement lorsque le nombre glouton est inférieur ou égal à students. Toute répartition qui convient avec L convient aussi avec L+1, donc la recherche dichotomique trouve la première limite qui convient.

L’intervalle commence par la plus grande valeur entre max(pages) et la part moyenne, total / students arrondie à l’entier supérieur, puisque la charge la plus lourde est au moins égale aux deux. La borne supérieure est total. Dans le premier exemple, l’intervalle va de 54 à 160, et la recherche essaie 107, 80, 67, 60, 64, 66 et 65.

Algorithme

Si students > pages.length, renvoie -1.
Additionne total et trouve le livre le plus épais. Définis lo comme étant le plus grand entre le livre le plus épais et (total + students - 1) / students, et hi = total.
Tant que lo < hi, prends mid = lo + (hi - lo) / 2.
Effectue le décompte glouton pour mid. S’il est inférieur ou égal à students, définis hi = mid ; sinon, définis lo = mid + 1.
Renvoie 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

Pièges et cas limites

Ignorer la vérification de -1. Pour [10, 20] et 3 étudiants, le décompte glouton avec une limite de 20 est de 2, donc la recherche renvoie 20.
Commencer l’intervalle uniquement à la part moyenne. Pour [1, 9] et 2 étudiants, la moyenne est de 5 et, à cette limite, l’approche gloutonne place le livre de 9 pages seul, compte 2 et renvoie 5.
Tester si le résultat est exactement égal à students. Pour [5, 5, 5, 5, 5, 5] et 4 étudiants, la réponse est 10, où le décompte glouton est de 3.
Trier les livres. [10, 1, 1, 10] avec 2 étudiants donne 11, mais trié en [1, 1, 10, 10], donne 12.

Questions fréquentes3

Le problème d’allocation de livres est-il identique au problème de la plus grande somme d’un tableau partagé ?

Oui. Les deux découpent un tableau en un nombre fixe de blocs contigus non vides et minimisent la somme du bloc le plus grand, et la même recherche binaire avec la même vérification gloutonne résout les deux problèmes. La version du livre ajoute le cas -1.

Quelle est la complexité temporelle du problème d’allocation des livres ?

Un temps de O(n log S) et un espace supplémentaire de O(1), où n est le nombre de livres et S le nombre total de pages. Chaque limite testée nécessite un parcours des livres, et la recherche teste environ log2 S limites : 29 pour une étagère de 5 × 10^8 pages.

Quand est-il impossible de répartir les livres ?

Uniquement lorsqu’il y a plus d’élèves que de livres, puisque chaque élève a besoin d’au moins un livre. Avec suffisamment de livres, tout bloc de deux livres ou plus peut donner son dernier livre à un élève qui n’en a aucun, jusqu’à ce que chacun en ait un.

def allocateBooks(pages, students):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu