Koko Eating Bananas

Q: Wie hoch ist die Zeitkomplexität von Koko Eating Bananas?

Die binäre Suche benötigt O(n log m) Zeit, wobei n die Anzahl der Stapel und m der größte Stapel ist: etwa log2(m) Prüfungen, 30 bei m = 10^9 , wobei jede Prüfung jeden Stapel einmal liest. Der zusätzliche Speicherbedarf beträgt O(1) .

Q: Was sind die untere und obere Schranke für die Geschwindigkeit?

Die obere Grenze ist der größte Haufen: Dort braucht jeder Haufen eine Stunde, was immer ausreicht. Die untere Grenze ist 1, und du kannst sie auf die Gesamtzahl der Bananen geteilt durch h , aufgerundet, erhöhen, weil Koko höchstens k Bananen pro Stunde isst.

Q: Wie teilst du und rundest mit Ganzzahlen auf?

Verwende (p + k-1) / k mit ganzzahliger Division. Durch das Addieren von k-1 wird jeder Rest über das nächste Vielfache von k hinausgeschoben, während ein genaues Vielfaches unverändert bleibt: 10 bei Geschwindigkeit 4 ergibt 13 / 4 = 3 , und 8 ergibt 11 / 4 = 2 . Gleitkommazahlen sind nicht erforderlich.

MittelBinäre Suche

+10

Koko hat n Bananenstapel, wobei sich piles[i] Bananen in Stapel i befinden, und h Stunden Zeit. Sie wählt eine Essgeschwindigkeit k, eine ganze Anzahl Bananen pro Stunde, und behält diese bei. Jede Stunde isst sie k Bananen aus einem Stapel; wenn sich in diesem Stapel weniger als k Bananen befinden, isst sie ihn vollständig auf und ruht sich aus, bis die Stunde vorbei ist. Gib das kleinste k zurück, mit dem sie alle Stapel innerhalb von h Stunden aufessen kann.

Funktion

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

pilesinteger-array: die Anzahl der Bananen in jedem Stapel
hinteger: die Anzahl der Stunden, die Koko hat
Gibt zurückinteger: die kleinste ganzzahlige Essgeschwindigkeit in Bananen pro Stunde, mit der alle Haufen innerhalb von h Stunden aufgegessen werden

Einschränkungen

1 ≤ piles.length ≤ 5000
1 ≤ piles[i] ≤ 10⁹
piles.length ≤ h ≤ 10⁹, also existiert immer eine Antwort.

Beispiele

Eingabe: piles = [4, 10, 7, 3]h = 6
Ausgabe: 5
Erklärung: Bei Geschwindigkeit 5 dauern die Stapel 4, 10, 7 und 3 jeweils 1, 2, 2 und 1 Stunden: insgesamt 6, was passt. Bei Geschwindigkeit 4 dauern sie 1, 3, 2 und 1 Stunden, also 7.

Weiterführende Frage

Verwandtes Problem: Koko isst ganze Haufen der Reihe nach, höchstens k Bananen pro Tag, innerhalb von d Tagen. Was ist das kleinste k, und was ändert sich bei deiner Suche?

Tipps

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

0 von 3 geöffnet

Lösung

Die Antwort ist eine Geschwindigkeit, keine Position im Array, und darin steckt eine binäre Suche. Eine Geschwindigkeit zu prüfen erfordert einen Durchlauf über die Haufen, und wenn Geschwindigkeit k rechtzeitig fertig wird, schafft das jede höhere Geschwindigkeit ebenfalls. Führe also eine binäre Suche über die Geschwindigkeiten von 1 bis zum größten Haufen durch: etwa 30 Prüfungen statt bis zu einer Milliarde.

Probiere jede Geschwindigkeit von 1 an aufwärts

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

Idee

Koko wechselt innerhalb einer Stunde nie zu einem anderen Haufen. Daher dauert es, einen Haufen mit p Bananen zu leeren, aufgerundet p / k Stunden: Bei einer Geschwindigkeit von 4 dauert es für 10 Bananen 3 Stunden. Probiere Geschwindigkeiten von 1, 2, 3 und so weiter aus und gib die erste zurück, bei der die Gesamtzeit in h passt. Sie ist die kleinste, weil jede niedrigere Geschwindigkeit nicht ausgereicht hat. Die Schleife endet spätestens bei der Geschwindigkeit des größten Haufens, bei der jeder Haufen eine Stunde dauert.

Ist m der größte Haufen, sind das bis zu m Prüfungen für jeweils n Haufen: etwa 5 × 10^12 Schritte bei 5000 Haufen mit jeweils fast 10^9 Bananen und h = 5000.

Algorithmus

Setze speed = 1.
Zähle die Stunden bei dieser Geschwindigkeit: Addiere für jeden Stapel (pile + speed-1) / speed zu einer 64-Bit-Summe.
Wenn die Summe höchstens h beträgt, gib speed zurück.
Andernfalls erhöhe speed um 1 und zähle erneut.

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

Binäre Suche nach der Geschwindigkeit

Idee

Wenn die Geschwindigkeit steigt, benötigt jeder Haufen gleich viele oder weniger Stunden. Daher lauten die Antworten auf „Reicht diese Geschwindigkeit aus, um rechtzeitig fertig zu werden?“ ab der ersten passenden Antwort: nein, nein, nein und dann ja. Die binäre Suche findet das erste Ja.

Behalte einen Bereich von lo bis hi bei, der immer die Antwort enthält. Beginne bei 1 und beim größten Haufen, dessen Geschwindigkeit eine Stunde pro Haufen benötigt und somit ausreicht. Wenn die mittlere Geschwindigkeit mid ausreicht, ist die Antwort mid oder langsamer, also setze hi = mid. Wenn nicht, reicht auch jede langsamere Geschwindigkeit nicht aus, also setze lo = mid + 1. Wenn lo hi erreicht, ist das die Antwort.

Im ersten Beispiel beginnt der Bereich bei 1 bis 10. Geschwindigkeit 5 reicht aus, also wird daraus 1 bis 5; bei Geschwindigkeit 3 dauert es 10 Stunden, also 4 bis 5; bei Geschwindigkeit 4 dauert es 7 Stunden, also 5 bis 5.

Algorithmus

Setze lo = 1 und hi auf den größten Stapel.
Solange lo < hi gilt, setze mid = lo + (hi - lo) / 2.
Zähle die Stunden bei Geschwindigkeit mid: Addiere für jeden Stapel (pile + mid-1) / mid zu einer 64-Bit-Summe.
Wenn die Summe höchstens h beträgt, setze hi = mid; andernfalls setze lo = mid + 1.
Gib lo zurück.

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

Stolperfallen und Grenzfälle

Überschreiten des Stundenlimits. Bei Geschwindigkeit 1 benötigen 5000 Haufen mit jeweils 10^9 Bananen 5 × 10^12 Stunden – mehr als das 32-Bit-Limit. Ein übergelaufener Gesamtwert kann dazu führen, dass eine zu langsame Geschwindigkeit als zulässig gilt. Zähle mit 64 Bit oder brich ab, sobald die Gesamtzeit h überschreitet.
Abrunden. 10 / 4 ergibt 2, doch für diesen Haufen werden 3 Stunden benötigt.
Den Suchbereich bei 0 beginnen lassen. Dann kann mid 0 sein und beim Zählen kommt es zu einer Division durch null.
hi = mid - 1 setzen, wenn mid passt. Dadurch kann die Antwort ausgeschlossen werden.
hi kleiner als den größten Haufen wählen. Wenn h der Anzahl der Haufen entspricht, ist jede niedrigere Geschwindigkeit ungeeignet, und die Suche gibt eine davon zurück.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Koko Eating Bananas?

Die binäre Suche benötigt O(n log m) Zeit, wobei n die Anzahl der Stapel und m der größte Stapel ist: etwa log2(m) Prüfungen, 30 bei m = 10^9, wobei jede Prüfung jeden Stapel einmal liest. Der zusätzliche Speicherbedarf beträgt O(1).

Was sind die untere und obere Schranke für die Geschwindigkeit?

Die obere Grenze ist der größte Haufen: Dort braucht jeder Haufen eine Stunde, was immer ausreicht. Die untere Grenze ist 1, und du kannst sie auf die Gesamtzahl der Bananen geteilt durch h, aufgerundet, erhöhen, weil Koko höchstens k Bananen pro Stunde isst.

Wie teilst du und rundest mit Ganzzahlen auf?

Verwende (p + k-1) / k mit ganzzahliger Division. Durch das Addieren von k-1 wird jeder Rest über das nächste Vielfache von k hinausgeschoben, während ein genaues Vielfaches unverändert bleibt: 10 bei Geschwindigkeit 4 ergibt 13 / 4 = 3, und 8 ergibt 11 / 4 = 2. Gleitkommazahlen sind nicht erforderlich.

def minEatingSpeed(piles, h):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argumente

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

Erwartete Ausgabe