Assign Cookies

Q: Jaka jest złożoność czasowa problemu Assign Cookies?

Sortowanie dwóch tablic kosztuje O(n log n + m log m) , a przejście dwoma wskaźnikami po sortowaniu ma złożoność O(n + m) , więc dominuje sortowanie. Sortowanie w miejscu utrzymuje dodatkowe zużycie pamięci na poziomie O(1) , pomijając pamięć używaną przez samo sortowanie.

Q: Dlaczego zachłanny wybór sprawdza się w zadaniu „Przydzielanie ciasteczek”?

Niech k będzie najmniejszym ciasteczkiem, które zadowoli najmniej łakome dziecko. Załóżmy, że w optymalnym przydziale to dziecko dostaje jakieś inne ciasteczko. Zamieńmy je: dziecko dostaje k , a ten, kto miał k , dostaje to drugie ciasteczko, które jest co najmniej tak duże jak k , więc nadal będzie najedzony. Liczba nie ulega zmianie, więc optymalny przydział zawsze może zaczynać się od zachłannego wyboru. Ten sam argument powtarza się dla pozostałych dzieci i ciasteczek.

ŁatweAlgorytmy zachłanne Sortowanie

+10

Każde dziecko i ma współczynnik łakomstwa g[i]: najmniejszy rozmiar ciastka, który je zadowoli. Każde ciastko j ma rozmiar s[j]. Dziecko jest zadowolone, gdy dostanie jedno ciastko, którego rozmiar jest co najmniej równy jego współczynnikowi łakomstwa. Każde dziecko dostaje najwyżej jedno ciastko, a każde ciastko trafia do najwyżej jednego dziecka. Zwróć maksymalną liczbę dzieci, które możesz zadowolić.

Funkcja

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

ginteger-array: współczynnik zachłanności każdego dziecka, najmniejszy rozmiar ciastka, który akceptuje
sinteger-array: rozmiar każdego ciasteczka
Zwracainteger: największa liczba dzieci, z których każde może dostać ciastko co najmniej tak duże, jak wynosi jego współczynnik łakomstwa

Ograniczenia

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Tablice mogą mieć różną długość i żadna z nich nie jest posortowana.

Przykłady

Wejście: g = [4, 2, 7]s = [3, 5, 1, 2]
Wyjście: 2
Wyjaśnienie: Po posortowaniu dzieci chcą odpowiednio 2, 4 i 7, a ciasteczka mają rozmiary 1, 2, 3 i 5. Ciasteczko o rozmiarze 2 zaspokaja dziecko, które chce 2, a ciasteczko o rozmiarze 5 zaspokaja dziecko, które chce 4. Nie ma już ciasteczka wystarczająco dużego dla dziecka, które chce 7, więc odpowiedź to 2.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

A co, jeśli każde dziecko ma też największe ciastko, które zaakceptuje, więc ciastko pasuje tylko w określonym przedziale? Któremu czekającemu dziecku należy wtedy dać każde ciastko?

Rozwiązanie

Pytanie brzmi: które dziecko powinno dostać które ciastko. Sprawdzanie każdej pary prowadzi do eksplozji liczby możliwości, ale jedna zachłanna zasada rozwiązuje problem: najpierw obsłuż najmniej wymagające dziecko i daj mu najmniejsze ciastko, które mu wystarczy. Po posortowaniu obu tablic ta zasada sprowadza się do jednego przejścia z dwoma wskaźnikami.

Najmniejsze odpowiednie ciasteczko dla każdego dziecka

Poprawne, ale nie kończy się na największych testach

Intuicja

Weź dzieci od najmniej łakomego do najbardziej łakomego. Dla każdego z nich przejrzyj wszystkie niewykorzystane jeszcze ciastka i wybierz najmniejsze, które jest wystarczająco duże. Jeśli żadne ciastko nie pasuje, to dziecko pozostaje głodne. W pierwszym przykładzie dzieci chcą odpowiednio 2, 4 i 7: dziecko, które chce 2, dostaje ciastko o rozmiarze 2, dziecko, które chce 4, dostaje ciastko o rozmiarze 5, a dla dziecka, które chce 7, nic już nie zostaje.

Dlaczego wybierać najmniejsze pasujące ciastko? Większe ciastko może nakarmić każde dziecko, które nakarmiłoby mniejsze, a także inne. Rozdawanie najmniejszych pasujących ciastek pozwala zachować większe dla bardziej łakomych dzieci, które pojawią się później, dzięki czemu nigdy nie stracisz możliwości nakarmienia dziecka.

Kosztem jest wyszukiwanie. Każde z n dzieci sprawdza wszystkie m ciastek, więc gdy n = m = 5000, daje to 25 milionów sprawdzeń — zbyt dużo w przypadku największych testów.

Algorytm

Posortuj współczynniki łakomstwa od najmniejszego do największego.
Dla każdego ciasteczka przechowuj flagę określającą, czy zostało użyte.
Dla każdego dziecka przejrzyj wszystkie ciasteczka i zapamiętaj najmniejsze nieużyte ciasteczko, którego rozmiar jest co najmniej równy łakomstwu dziecka.
Jeśli znajdziesz takie ciasteczko, oznacz je jako użyte i zalicz dziecko jako zadowolone.
Zwróć liczbę.

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

Posortuj oba i użyj dwóch wskaźników

Intuicja

Powyższe skanowanie wciąż od nowa szuka najmniejszego pasującego ciasteczka. Posortuj także ciasteczka, a to wyszukiwanie zniknie: ciasteczka są uporządkowane według rosnącego rozmiaru, więc najpierw napotkasz najmniejsze pasujące ciasteczko.

Przeglądaj ciasteczka od najmniejszego do największego i używaj jednego wskaźnika, child, wskazującego najmniej łakome dziecko, które wciąż czeka. Jeśli ciasteczko ma rozmiar co najmniej g[child], dziecko dostaje ciasteczko, a wskaźnik przechodzi do następnego dziecka. Jeśli jest mniejsze, to jest też mniejsze od każdego wciąż czekającego dziecka, ponieważ są one posortowane, więc ciasteczko jest bezużyteczne i przechodzisz dalej.

W pierwszym przykładzie posortowane ciasteczka mają rozmiary 1, 2, 3, 5, a posortowane zachcianki to 2, 4, 7. Ciasteczko 1 jest za małe dla 2. Ciasteczko 2 zaspokaja dziecko, które chce 2. Ciasteczko 3 jest za małe dla 4. Ciasteczko 5 zaspokaja dziecko, które chce 4. Wskaźnik zatrzymuje się na 2 — to odpowiedź.

Każdy wskaźnik przesuwa się tylko do przodu, więc przejście ma złożoność O(n + m), a dominują dwa sortowania. Sortowanie w miejscu nie wymaga dodatkowych tablic.

Algorytm

Posortuj g i s rosnąco.
Ustaw child = 0 — najmniej zachłanne dziecko, które wciąż czeka.
Dla każdego ciasteczka, zaczynając od najmniejszego: jeśli child nadal mieści się w g, a ciasteczko ma rozmiar co najmniej g[child], zwiększ child o 1.
Zwróć child — liczbę nakarmionych dzieci.

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

Pułapki i przypadki brzegowe

Większość błędnych odpowiedzi wynika z dobierania w niewłaściwej kolejności albo przesuwania niewłaściwego wskaźnika.

Podanie dziecku większego ciasteczka, niż potrzebuje. Przy g = [1, 2] i s = [1, 3] podanie ciasteczka 3 dziecku, które chce 1, sprawia, że dziecko, które chce 2, pozostaje głodne, podczas gdy właściwe dopasowanie nakarmiłoby oboje.
Przesuwanie wskaźnika dziecka, gdy ciasteczko jest za małe. Dziecko nadal potrzebuje ciasteczka — to ciasteczko jest bezużyteczne.
Zapominanie o sprawdzeniu granicy dla wskaźnika dziecka. Gdy każde dziecko jest już nakarmione, pozostałe ciasteczka nie mogą powodować odczytu poza końcem g.
Porównywanie za pomocą > zamiast ≥. Ciasteczko dokładnie tej wielkości co współczynnik łakomstwa wystarczy.
Sortowanie liczb jak tekstu. W JavaScript sort() bez komparatora umieszcza 10 przed 9.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu Assign Cookies?

Sortowanie dwóch tablic kosztuje O(n log n + m log m), a przejście dwoma wskaźnikami po sortowaniu ma złożoność O(n + m), więc dominuje sortowanie. Sortowanie w miejscu utrzymuje dodatkowe zużycie pamięci na poziomie O(1), pomijając pamięć używaną przez samo sortowanie.

Dlaczego zachłanny wybór sprawdza się w zadaniu „Przydzielanie ciasteczek”?

Niech k będzie najmniejszym ciasteczkiem, które zadowoli najmniej łakome dziecko. Załóżmy, że w optymalnym przydziale to dziecko dostaje jakieś inne ciasteczko. Zamieńmy je: dziecko dostaje k, a ten, kto miał k, dostaje to drugie ciasteczko, które jest co najmniej tak duże jak k, więc nadal będzie najedzony. Liczba nie ulega zmianie, więc optymalny przydział zawsze może zaczynać się od zachłannego wyboru. Ten sam argument powtarza się dla pozostałych dzieci i ciasteczek.

Czy możesz zamiast tego zacząć od najbardziej łakomego dziecka?

Tak. Posortuj obie tablice, a następnie przechodź od największego ciasteczka i najbardziej łakomego dziecka: jeśli największe pozostałe ciasteczko pasuje do najbardziej łakomego pozostałego dziecka, nakarm je i przesuń oba wskaźniki; jeśli nie, żadne ciasteczko nie nakarmi tego dziecka, więc je pomiń. Uzyskasz tę samą liczbę w tym samym czasie.

Czy Assign Cookies to problem programowania dynamicznego?

Nie. Argument zamiany pokazuje, że wybór zachłanny jest zawsze bezpieczny, więc sortowanie i jedno przejście wystarczą, w czasie O(n log n + m log m). Tabela oparta na dwóch posortowanych tablicach, wypełniana tak jak tabela najdłuższego wspólnego podciągu, również znajduje odpowiedź, ale uzyskanie tego samego wyniku kosztuje O(n × m).

Python

def findContentChildren(g, s):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Wejście

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

Oczekiwane