Book Allocation Problem

Q: Ist das Buchzuordnungsproblem dasselbe wie „Split Array Largest Sum“?

Ja. Beide teilen ein Array in eine feste Anzahl nicht leerer zusammenhängender Blöcke auf und minimieren die Summe des größten Blocks. Beide lassen sich mit derselben binären Suche und derselben Greedy-Prüfung lösen. Die Buchversion ergänzt den Fall -1 .

Q: Wie hoch ist die Zeitkomplexität des Book Allocation Problems?

O(n log S) Zeit und O(1) zusätzlicher Speicherplatz, wobei n die Anzahl der Bücher und S die Gesamtseitenzahl ist. Jeder getestete Grenzwert erfordert einen Durchlauf über die Bücher, und die Suche testet etwa log2 S Grenzwerte: 29 bei einem Regal mit 5 × 10^8 Seiten.

Q: Wann ist es unmöglich, die Bücher zuzuordnen?

Nur wenn es mehr Schüler als Bücher gibt, da jeder Schüler mindestens ein Buch benötigt. Wenn genügend Bücher vorhanden sind, kann jeder Block aus zwei oder mehr Büchern sein letztes Buch einem Schüler ohne Buch geben, bis jeder eines hat.

MittelBinäre Suche Greedy

+10

Ein Regal enthält Bücher in einer festen Reihenfolge, und pages[i] ist die Anzahl der Seiten im Buch i. Teile die Bücher unter students Studierenden auf: Jeder Student erhält eine zusammenhängende Reihe benachbarter Bücher, mindestens ein Buch, und jedes Buch wird genau einem Studenten zugeteilt. Die Arbeitslast eines Studenten ist die Gesamtzahl der Seiten, die er erhält.

Gib den kleinstmöglichen Wert der höchsten Arbeitslast zurück. Wenn es mehr Studierende als Bücher gibt, gib -1 zurück.

Funktion

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

pagesinteger-array: die Seitenzahl jedes Buches, in Regalreihenfolge
studentsinteger: die Anzahl der Schüler, die sich die Bücher teilen
Gibt zurückinteger: die kleinstmögliche maximale Last oder -1, wenn es mehr Schüler als Bücher gibt

Einschränkungen

1 ≤ pages.length ≤ 5000
1 ≤ pages[i] ≤ 10⁵
1 ≤ students ≤ 10⁴
Gib -1 zurück, wenn students > pages.length.

Beispiele

Eingabe: pages = [25, 40, 15, 30, 50]students = 3
Ausgabe: 65
Erklärung: Gib [25, 40], [15, 30] und [50] aus: Die Auslastungen betragen 65, 45 und 50. Ein Limit von 64 schlägt fehl: Bei der Ausgabe erhalten vier Schüler [25], [40, 15], [30], [50].

Eingabe: pages = [10, 20]students = 3
Ausgabe: -1
Erklärung: Zwei Bücher können nicht drei Schülern jeweils ein Buch geben, daher lautet die Antwort -1.

Weiterführende Frage

Beweise, dass der aufgerundete durchschnittliche Anteil plus das dickste Buch immer eine brauchbare Obergrenze ist. Wie viele Prüfungen erspart diese Obergrenze bei einem Regal mit dünnen Büchern?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Es gibt zu viele Möglichkeiten, das Regal aufzuteilen, aber eine einzelne Seitenbegrenzung zu testen, ist einfach: Gib die Bücher in der Reihenfolge im Regal aus und gehe zum nächsten Schüler über, sobald ein Buch die Begrenzung überschreiten würde. Zähle dann die Schüler. Bei einer höheren Begrenzung werden nie mehr Schüler benötigt, daher bilden die passenden Begrenzungen einen zusammenhängenden Bereich, und mit binärer Suche findest du dessen Anfang.

Erhöhe das Seitenlimit jeweils um eine Seite

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Beginne bei L = max(pages), da jemand das dickste Buch trägt, und erhöhe L Seite für Seite, bis die gierige Anzahl in students passt. Jede niedrigere Grenze ist gescheitert, also ist die erste, die passt, die Antwort. Im ersten Beispiel werden bei jeder Grenze von 50 bis 64 vier Studierende benötigt und bei 65 drei: 16 Prüfungen.

Die Antwort kann das ganze Regal sein: Ein Studierender und 5000 Bücher mit jeweils 10^5 Seiten bedeuten etwa 5 × 10^8 Grenzen, von denen jede einen Durchlauf über 5000 Bücher erfordert. In der Zeitspalte ist A die Antwort und m das dickste Buch.

Algorithmus

Wenn students > pages.length gilt, gib -1 zurück.
Schreibe die gierige Zählung für eine Grenze L: Beginne mit einem Studenten und einer Last von 0; wenn load + pages[i] > L gilt, füge einen Studenten hinzu und setze die Last auf pages[i], andernfalls addiere das Buch zur Last.
Setze L auf das dickste Buch.
Solange die Zählung für L größer als students ist, addiere 1 zu L.
Gib L zurück.

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

Binäre Suche auf das Seitenlimit

Idee

Die Greedy-Anzahl ist die kleinste Anzahl an Schülern, die eine beliebige Aufteilung unter L verwenden kann. Vergleicht man sie Schüler für Schüler mit einer beliebigen anderen Aufteilung, hört jeder Greedy-Schüler erst auf, wenn das nächste Buch nicht mehr passt, und kommt daher mindestens genauso weit im Bücherregal. Weniger Schüler als vorhanden sind kein Problem: Ein Schüler, der zwei Bücher hält, kann eines an einen Schüler ohne Buch weitergeben, ohne dass die Last eines Schülers zunimmt.

L funktioniert also genau dann, wenn die Greedy-Anzahl höchstens students beträgt. Was unter L funktioniert, funktioniert auch unter L+1, daher findet die binäre Suche die kleinste funktionierende Grenze.

Der Bereich beginnt beim größeren Wert aus max(pages) und dem aufgerundeten durchschnittlichen Anteil, total / students, da die größte Last mindestens so groß wie beide Werte ist. Der obere Grenzwert ist total. Im ersten Beispiel reicht der Bereich von 54 bis 160, und die Suche probiert 107, 80, 67, 60, 64, 66 und 65 aus.

Algorithmus

Wenn students > pages.length, gib -1 zurück.
Addiere total und finde das dickste Buch. Setze lo auf den größeren Wert aus dem dicksten Buch und (total + students - 1) / students, und hi = total.
Solange lo < hi gilt, berechne mid = lo + (hi - lo) / 2.
Führe die Greedy-Zählung für mid aus. Wenn sie höchstens students beträgt, setze hi = mid; andernfalls setze lo = mid + 1.
Gib lo zurück.

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

Stolperfallen und Grenzfälle

Die Prüfung auf -1 überspringen. Für [10, 20] und 3 Studierende beträgt die gierige Anzahl bei einem Grenzwert von 20 2, daher gibt die Suche 20 zurück.
Den Bereich allein beim durchschnittlichen Anteil beginnen lassen. Für [1, 9] und 2 Studierende beträgt der Durchschnitt 5, und dort weist das gierige Verfahren das Buch mit 9 Seiten allein zu, zählt 2 und gibt 5 zurück.
Auf genau students testen. Für [5, 5, 5, 5, 5, 5] und 4 Studierende lautet die Antwort 10, wobei die gierige Anzahl 3 beträgt.
Die Bücher sortieren. [10, 1, 1, 10] ergibt mit 2 Studierenden 11, sortiert zu [1, 1, 10, 10] ergibt es jedoch 12.

Häufige Fragen3

Ist das Buchzuordnungsproblem dasselbe wie „Split Array Largest Sum“?

Ja. Beide teilen ein Array in eine feste Anzahl nicht leerer zusammenhängender Blöcke auf und minimieren die Summe des größten Blocks. Beide lassen sich mit derselben binären Suche und derselben Greedy-Prüfung lösen. Die Buchversion ergänzt den Fall -1.

Wie hoch ist die Zeitkomplexität des Book Allocation Problems?

O(n log S) Zeit und O(1) zusätzlicher Speicherplatz, wobei n die Anzahl der Bücher und S die Gesamtseitenzahl ist. Jeder getestete Grenzwert erfordert einen Durchlauf über die Bücher, und die Suche testet etwa log2 S Grenzwerte: 29 bei einem Regal mit 5 × 10^8 Seiten.

Wann ist es unmöglich, die Bücher zuzuordnen?

Nur wenn es mehr Schüler als Bücher gibt, da jeder Schüler mindestens ein Buch benötigt. Wenn genügend Bücher vorhanden sind, kann jeder Block aus zwei oder mehr Büchern sein letztes Buch einem Schüler ohne Buch geben, bis jeder eines hat.

def allocateBooks(pages, students):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe