Assign Cookies

Q: Qual è la complessità temporale di Assign Cookies?

Ordinare i due array costa O(n log n + m log m) e la scansione con due puntatori successiva costa O(n + m) , quindi sono gli ordinamenti a dominare. Ordinare sul posto mantiene lo spazio aggiuntivo a O(1) , a parte quello usato dall’ordinamento stesso.

Q: Perché la scelta greedy funziona per Assegnare biscotti?

Sia k il biscotto più piccolo che soddisfa il bambino meno esigente. Supponiamo che un'assegnazione ottimale dia a quel bambino un altro biscotto. Scambiamoli: il bambino prende k , e chi aveva k prende l'altro biscotto, che è almeno grande quanto k , quindi rimane sazio. Il numero non cambia, perciò un'assegnazione ottimale può sempre iniziare con la scelta più avara, e lo stesso ragionamento si ripete per i bambini e i biscotti rimanenti.

FacileGreedy Ordinamento

+10

Ogni bambino i ha un fattore di avidità g[i]: la dimensione minima del biscotto che lo rende felice. Ogni biscotto j ha una dimensione s[j]. Un bambino è soddisfatto quando riceve un biscotto la cui dimensione è almeno pari al suo fattore di avidità. Ogni bambino riceve al massimo un biscotto e ogni biscotto viene assegnato al massimo a un bambino. Restituisci il numero massimo di bambini che puoi soddisfare.

Funzione

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

ginteger-array: il fattore di avidità di ogni bambino, la dimensione più piccola del biscotto che accetta
sinteger-array: la dimensione di ogni cookie
Restituisceinteger: il maggior numero di bambini che possono ricevere ciascuno un biscotto grande almeno quanto il loro fattore di avidità

Vincoli

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
I due array possono avere lunghezze diverse e nessuno dei due è ordinato.

Esempi

Input: g = [4, 2, 7]s = [3, 5, 1, 2]
Output: 2
Spiegazione: Ordinati, i bambini vogliono 2, 4 e 7 e i biscotti sono 1, 2, 3 e 5. Il biscotto 2 sfama il bambino che vuole 2 e il biscotto 5 sfama il bambino che vuole 4. Non rimane nulla che raggiunga 7, quindi la risposta è 2.

+16 test nascosti all’invio

Per approfondire

E se ogni bambino avesse anche un biscotto più grande che è disposto ad accettare, così che un biscotto possa rientrare solo in un intervallo? A quale bambino in attesa dovrebbe essere assegnato allora ogni biscotto?

Soluzione

La domanda è quale bambino debba ricevere quale biscotto. Provare ogni abbinamento fa esplodere il numero di possibilità, ma una semplice regola greedy risolve il problema: servi prima il bambino meno esigente e dagli il biscotto più piccolo che sia sufficiente. Dopo aver ordinato entrambi gli array, la regola si traduce in un'unica scansione con due puntatori.

Il biscotto più piccolo adatto a ogni bambino

Corretto, ma non termina sui test più grandi

Intuizione

Prendi i bambini dal meno al più goloso. Per ognuno, esamina tutti i biscotti ancora inutilizzati e scegli il più piccolo che sia abbastanza grande. Se nessun biscotto è adatto, quel bambino resta affamato. Nel primo esempio i bambini vogliono 2, 4 e 7: il bambino che vuole 2 riceve il biscotto 2, quello che vuole 4 riceve il biscotto 5 e non resta nulla per quello che vuole 7.

Perché scegliere il biscotto più piccolo che va bene? Un biscotto più grande può sfamare tutti i bambini che può sfamare quello più piccolo, e anche altri. Distribuire il biscotto più piccolo che va bene lascia quelli più grandi ai bambini più golosi che verranno dopo, così non rinunci mai a sfamare un bambino che avresti potuto sfamare.

Il costo è la ricerca. Ognuno degli n bambini esamina tutti gli m biscotti, quindi con n = m = 5000 si fanno 25 milioni di controlli: troppi per i test più grandi.

Algoritmo

Ordina i fattori di avidità dal più piccolo al più grande.
Tieni un flag per ogni biscotto che indica se è stato usato.
Per ogni bambino, esamina tutti i biscotti e ricorda quello non usato più piccolo la cui dimensione sia almeno pari all'avidità del bambino.
Se ne hai trovato uno, contrassegnalo come usato e conta il bambino come soddisfatto.
Restituisci il conteggio.

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

Ordina entrambi e usa due puntatori

Intuizione

La scansione qui sopra cerca ancora e ancora il biscotto più piccolo che va bene. Ordina anche i biscotti e la ricerca scompare: i biscotti sono in ordine crescente di dimensione, quindi incontri per primo il biscotto più piccolo che va bene.

Esamina i biscotti dal più piccolo al più grande e mantieni un puntatore, child, sul bambino meno esigente ancora in attesa. Se il biscotto è almeno pari a g[child], quel bambino viene accontentato e il puntatore passa al bambino successivo. Se è più piccolo, è più piccolo anche di tutti i bambini ancora in attesa, poiché sono ordinati, quindi il biscotto è inutile e passi oltre.

Nel primo esempio i biscotti ordinati sono 1, 2, 3, 5 e i livelli di avidità ordinati sono 2, 4, 7. Il biscotto 1 è troppo piccolo per 2. Il biscotto 2 accontenta il bambino che vuole 2. Il biscotto 3 è troppo piccolo per 4. Il biscotto 5 accontenta il bambino che vuole 4. Il puntatore si ferma a 2, la risposta.

Ogni puntatore si sposta solo in avanti, quindi la scansione è O(n + m) e i due ordinamenti dominano. Ordinare sul posto non richiede array aggiuntivi.

Algoritmo

Ordina g e s in ordine crescente.
Imposta child = 0, il bambino meno esigente ancora in attesa.
Per ogni biscotto, dal più piccolo: se child è ancora dentro g e il biscotto è almeno pari a g[child], aggiungi 1 a child.
Restituisci child, il numero di bambini sfamati.

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

Trappole e casi limite

La maggior parte delle risposte sbagliate deriva dall’abbinare nell’ordine sbagliato o dallo spostare il puntatore sbagliato.

Dare a un bambino un biscotto più grande di quello di cui ha bisogno. Con g = [1, 2] e s = [1, 3], dare il biscotto 3 al bambino che ne vuole 1 lascia affamato il bambino che ne vuole 2, mentre l’abbinamento corretto sfama entrambi.
Spostare il puntatore del bambino quando un biscotto è troppo piccolo. Il bambino ha ancora bisogno di un biscotto; è il biscotto a essere inutile.
Dimenticare il controllo dei limiti sul puntatore del bambino. Una volta sfamati tutti i bambini, i biscotti rimanenti non devono leggere oltre la fine di g.
Confrontare con > invece che con ≥. Un biscotto grande esattamente quanto il fattore di avidità è sufficiente.
Ordinare i numeri come testo. In JavaScript, sort() senza un comparatore mette 10 prima di 9.

Domande frequenti4

Qual è la complessità temporale di Assign Cookies?

Ordinare i due array costa O(n log n + m log m) e la scansione con due puntatori successiva costa O(n + m), quindi sono gli ordinamenti a dominare. Ordinare sul posto mantiene lo spazio aggiuntivo a O(1), a parte quello usato dall’ordinamento stesso.

Perché la scelta greedy funziona per Assegnare biscotti?

Sia k il biscotto più piccolo che soddisfa il bambino meno esigente. Supponiamo che un'assegnazione ottimale dia a quel bambino un altro biscotto. Scambiamoli: il bambino prende k, e chi aveva k prende l'altro biscotto, che è almeno grande quanto k, quindi rimane sazio. Il numero non cambia, perciò un'assegnazione ottimale può sempre iniziare con la scelta più avara, e lo stesso ragionamento si ripete per i bambini e i biscotti rimanenti.

Puoi invece partire dal bambino più ingordo?

Sì. Ordina entrambi gli array, poi procedi partendo dal biscotto più grande e dal bambino più ingordo: se il biscotto più grande rimasto è sufficiente per il bambino più ingordo rimasto, dai da mangiare a entrambi e sposta entrambi gli indici; altrimenti, quel bambino non può essere sfamato con nessun biscotto, quindi saltalo. Si ottiene lo stesso conteggio nello stesso tempo.

Assegnare i cookie è un problema di programmazione dinamica?

No. Un argomento di scambio dimostra che la scelta greedy è sempre sicura, quindi bastano l'ordinamento e una sola scansione, in O(n log n + m log m). Anche una tabella sulle due matrici ordinate, compilata come una tabella della sottosequenza comune più lunga, trova la risposta, ma richiede O(n × m) di tempo per ottenere lo stesso risultato.

Python

def findContentChildren(g, s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

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

Atteso