Assign Cookies

Q: Wie hoch ist die Zeitkomplexität von Assign Cookies?

Das Sortieren der beiden Arrays kostet O(n log n + m log m) , und der anschließende Durchlauf mit zwei Zeigern benötigt O(n + m) , sodass die Sortierungen den Aufwand bestimmen. In-place-Sortieren hält den zusätzlichen Speicherbedarf bei O(1) , abgesehen von dem Speicher, den die Sortierung selbst verwendet.

Q: Warum funktioniert die Greedy-Entscheidung bei Assign Cookies?

Sei k der kleinste Keks, der für das am wenigsten gierige Kind ausreicht. Angenommen, eine optimale Zuordnung gibt diesem Kind einen anderen Keks. Tausche: Das Kind bekommt k , und wer zuvor k hatte, bekommt den anderen Keks, der mindestens so groß wie k ist, sodass diese Person weiterhin satt wird. Die Anzahl ändert sich nicht, daher kann eine optimale Zuordnung immer mit der gierigen Wahl beginnen, und dasselbe Argument lässt sich für die übrigen Kinder und Kekse wiederholen.

LeichtGreedy Sortieren

+10

Jedes Kind i hat einen Anspruchsfaktor g[i]: die kleinste Keksgröße, die es zufriedenstellt. Jeder Keks j hat eine Größe s[j]. Ein Kind ist zufrieden, wenn es einen Keks bekommt, dessen Größe mindestens seinem Anspruchsfaktor entspricht. Jedes Kind bekommt höchstens einen Keks, und jeder Keks geht an höchstens ein Kind. Gib die größtmögliche Anzahl an Kindern zurück, die du zufriedenstellen kannst.

Funktion

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: der Gierfaktor jedes Kindes, die kleinste Keksgröße, die es akzeptiert
sinteger-array: die Größe jedes Cookies
Gibt zurückinteger: die größtmögliche Anzahl an Kindern, die jeweils einen Keks erhalten können, der mindestens so groß ist wie ihr Gierfaktor

Einschränkungen

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Die beiden Arrays können unterschiedliche Längen haben, und keines von ihnen ist sortiert.

Beispiele

Eingabe: g = [4, 2, 7]s = [3, 5, 1, 2]
Ausgabe: 2
Erklärung: Sortiert möchten die Kinder 2, 4 und 7, und die Kekse haben die Größen 1, 2, 3 und 5. Keks 2 macht das Kind satt, das 2 möchte, und Keks 5 macht das Kind satt, das 4 möchte. Es bleibt nichts übrig, das für 7 reicht, also lautet die Antwort 2.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Was ist, wenn jedes Kind auch einen größten Keks hat, den es annimmt, sodass ein Keks nur in einen bestimmten Größenbereich passt? Welches wartende Kind sollte dann welchen Keks bekommen?

Lösung

Die Frage ist, welches Kind welchen Keks bekommen soll. Alle Kombinationen auszuprobieren, führt zu einer riesigen Anzahl von Möglichkeiten, aber eine einzige gierige Regel löst das Problem: Bediene zuerst das am wenigsten gierige Kind und gib ihm den kleinsten Keks, der passt. Nachdem beide Arrays sortiert wurden, wird aus dieser Regel ein einziger Durchlauf mit zwei Zeigern.

Kleinster passender Keks für jedes Kind

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

Idee

Nimm die Kinder vom genügsamsten bis zum gierigsten. Gehe für jedes Kind alle Kekse durch, die noch nicht vergeben wurden, und wähle den kleinsten, der groß genug ist. Passt kein Keks, bleibt dieses Kind hungrig. Im ersten Beispiel wollen die Kinder 2, 4 und 7: Das Kind, das 2 möchte, bekommt Keks 2, das Kind, das 4 möchte, bekommt Keks 5, und für 7 bleibt nichts übrig.

Warum der kleinste passende Keks? Ein größerer Keks kann jedes Kind satt machen, das auch der kleinere satt machen kann – und noch mehr. Wenn du den kleinsten passenden Keks ausgibst, bleiben die größeren Kekse für die gierigeren Kinder übrig, die später drankommen. So verlierst du nie ein Kind, das du hättest satt machen können.

Der Aufwand liegt in der Suche. Jedes der n Kinder durchsucht alle m Kekse. Bei n = m = 5000 sind das 25 Millionen Prüfungen – zu langsam für die größten Tests.

Algorithmus

Sortiere die Gierfaktoren vom kleinsten zum größten.
Vermerke für jeden Keks, ob er verwendet wird.
Gehe für jedes Kind alle Kekse durch und merke dir den kleinsten unbenutzten Keks, dessen Größe mindestens dem Gierfaktor des Kindes entspricht.
Wenn du einen gefunden hast, markiere ihn als verwendet und zähle das Kind als zufriedengestellt.
Gib die Anzahl zurück.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Sortiere beide und verwende zwei Zeiger

Idee

Die obige Suche sucht immer wieder nach dem kleinsten passenden Keks. Sortiere auch die Kekse, dann entfällt diese Suche: Die Kekse kommen in aufsteigender Größe, sodass du zuerst auf den kleinsten passenden Keks triffst.

Gehe die Kekse vom kleinsten zum größten durch und behalte einen Zeiger, child, auf das am wenigsten gierige Kind, das noch wartet. Wenn der Keks mindestens g[child] groß ist, wird dieses Kind satt und der Zeiger rückt zum nächsten Kind weiter. Ist der Keks kleiner, ist er auch kleiner als jeder andere noch wartende Keks, da sie sortiert sind. Der Keks ist also nutzlos, und du gehst weiter.

Im ersten Beispiel sind die sortierten Kekse 1, 2, 3, 5 und die sortierten Gierwerte 2, 4, 7. Keks 1 ist zu klein für 2. Keks 2 macht das Kind satt, das 2 möchte. Keks 3 ist zu klein für 4. Keks 5 macht das Kind satt, das 4 möchte. Der Zeiger bleibt bei 2 stehen, der Antwort.

Jeder Zeiger bewegt sich nur vorwärts, also ist der Durchlauf O(n + m), und die beiden Sortierungen bestimmen den Aufwand. Beim Sortieren an Ort und Stelle sind keine zusätzlichen Arrays nötig.

Algorithmus

Sortiere g und s in aufsteigender Reihenfolge.
Setze child = 0, das am wenigsten gierige Kind, das noch wartet.
Für jeden Keks, beginnend mit dem kleinsten: Wenn child noch innerhalb von g liegt und der Keks mindestens so groß wie g[child] ist, erhöhe child um 1.
Gib child zurück, die Anzahl der versorgten Kinder.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen dadurch, dass die Zuordnungen in der falschen Reihenfolge vorgenommen oder der falsche Zeiger verschoben wird.

Einem Kind einen größeren Keks zu geben, als es braucht. Bei g = [1, 2] und s = [1, 3] lässt der Keks 3 für das Kind, das 1 möchte, das Kind, das 2 möchte, hungrig zurück, während die richtige Zuordnung beide satt macht.
Den Zeiger des Kindes weiterzusetzen, wenn ein Keks zu klein ist. Das Kind braucht weiterhin einen Keks; der Keks ist es, der nicht zu gebrauchen ist.
Die Grenzprüfung für den Zeiger des Kindes zu vergessen. Sobald alle Kinder satt sind, darf beim Prüfen der übrigen Kekse nicht über das Ende von g hinausgelesen werden.
Mit > statt mit ≥ zu vergleichen. Ein Keks, der genau so groß wie der Gierfaktor ist, reicht aus.
Zahlen als Text zu sortieren. In JavaScript setzt sort() ohne Vergleichsfunktion die 10 vor die 9.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Assign Cookies?

Das Sortieren der beiden Arrays kostet O(n log n + m log m), und der anschließende Durchlauf mit zwei Zeigern benötigt O(n + m), sodass die Sortierungen den Aufwand bestimmen. In-place-Sortieren hält den zusätzlichen Speicherbedarf bei O(1), abgesehen von dem Speicher, den die Sortierung selbst verwendet.

Warum funktioniert die Greedy-Entscheidung bei Assign Cookies?

Sei k der kleinste Keks, der für das am wenigsten gierige Kind ausreicht. Angenommen, eine optimale Zuordnung gibt diesem Kind einen anderen Keks. Tausche: Das Kind bekommt k, und wer zuvor k hatte, bekommt den anderen Keks, der mindestens so groß wie k ist, sodass diese Person weiterhin satt wird. Die Anzahl ändert sich nicht, daher kann eine optimale Zuordnung immer mit der gierigen Wahl beginnen, und dasselbe Argument lässt sich für die übrigen Kinder und Kekse wiederholen.

Kannst du stattdessen beim gierigsten Kind anfangen?

Ja. Sortiere beide Arrays und gehe dann vom größten Keks und dem gierigsten Kind aus vor: Wenn der größte verbleibende Keks für das gierigste verbleibende Kind reicht, gib ihm den Keks und rücke beide Zeiger weiter; wenn nicht, kann dieses Kind mit keinem Keks satt gemacht werden, also überspringe das Kind. Das ergibt dieselbe Anzahl in derselben Zeit.

Ist „Assign Cookies“ ein Problem der dynamischen Programmierung?

Nein. Ein Vertauschungsargument zeigt, dass die gierige Wahl immer sicher ist. Daher reicht es, zu sortieren und einmal durchzugehen, in O(n log n + m log m). Eine Tabelle über die beiden sortierten Arrays, die wie eine Tabelle für die längste gemeinsame Teilfolge gefüllt wird, findet die Antwort ebenfalls, benötigt für dasselbe Ergebnis aber eine Laufzeit von O(n × m).

Python

def findContentChildren(g, s):
    # Schreibe hier Code

Testfälle

Fall 1

Fall 2

Eingabe

g = [4, 2, 7]
s = [3, 5, 1, 2]

Erwartet