Assign Cookies

Q: Quelle est la complexité temporelle de Assign Cookies ?

Le tri des deux tableaux coûte O(n log n + m log m) , et le parcours à deux pointeurs qui suit coûte O(n + m) , donc ce sont les tris qui dominent. Le tri sur place maintient l’espace supplémentaire à O(1) , hormis celui utilisé par le tri lui-même.

Q: Pourquoi le choix glouton fonctionne-t-il pour Assign Cookies ?

Soit k le plus petit biscuit qui convient à l’enfant le moins gourmand. Supposons qu’une attribution optimale donne à cet enfant un autre biscuit. Échangeons-les : l’enfant prend k , et celui qui avait k prend l’autre biscuit, qui est au moins aussi grand que k , et reste donc rassasié. Le nombre ne change pas ; une attribution optimale peut donc toujours commencer par le choix glouton, et le même raisonnement se répète pour les enfants et les biscuits restants.

FacileGlouton Tri

+10

Chaque enfant i a un facteur de gourmandise g[i] : la plus petite taille de biscuit qui le rend heureux. Chaque biscuit j a une taille s[j]. Un enfant est satisfait lorsqu’il reçoit un biscuit dont la taille est au moins égale à son facteur de gourmandise. Chaque enfant reçoit au maximum un biscuit et chaque biscuit est attribué à au maximum un enfant. Retournez le nombre maximal d’enfants que vous pouvez satisfaire.

Fonction

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

ginteger-array: le facteur de gourmandise de chaque enfant, la plus petite taille de biscuit qu’il accepte
sinteger-array: la taille de chaque cookie
Renvoieinteger: le nombre maximal d’enfants pouvant chacun recevoir un cookie au moins aussi grand que leur facteur de gourmandise

Contraintes

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Les deux tableaux peuvent avoir des longueurs différentes, et aucun des deux n’est trié.

Exemples

Entrée: g = [4, 2, 7]s = [3, 5, 1, 2]
Sortie: 2
Explication: Après le tri, les enfants veulent 2, 4 et 7, et les biscuits sont de taille 1, 2, 3 et 5. Le biscuit 2 nourrit l’enfant qui en veut 2 et le biscuit 5 nourrit l’enfant qui en veut 4. Il ne reste rien qui puisse satisfaire celui qui en veut 7, donc la réponse est 2.

+16 tests cachés à la soumission

Pour aller plus loin

Et si chaque enfant avait aussi un plus gros biscuit qu’il accepterait, de sorte qu’un biscuit ne convienne que dans une certaine plage ? À quel enfant en attente faut-il alors donner chaque biscuit ?

Solution

La question est de savoir quel enfant doit recevoir quel biscuit. Essayer toutes les associations entraîne une explosion du nombre de possibilités, mais une règle gloutonne suffit à trancher : servir d’abord l’enfant le moins gourmand et lui donner le plus petit biscuit qui lui convient. Après avoir trié les deux tableaux, cette règle se traduit par un seul parcours avec deux pointeurs.

Le plus petit cookie adapté à chaque enfant

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Prenez les enfants du moins gourmand au plus gourmand. Pour chacun, parcourez tous les biscuits qui n’ont pas encore été utilisés et choisissez le plus petit qui soit assez grand. Si aucun biscuit ne convient, l’enfant reste affamé. Dans le premier exemple, les enfants veulent 2, 4 et 7 : celui qui veut 2 reçoit le biscuit 2, celui qui veut 4 reçoit le biscuit 5, et il ne reste rien pour celui qui veut 7.

Pourquoi choisir le plus petit biscuit qui convient ? Un biscuit plus gros peut nourrir tous les enfants que le plus petit peut nourrir, et davantage. En distribuant le plus petit biscuit qui convient, vous gardez les plus gros pour les enfants plus gourmands qui viennent ensuite, et vous ne perdez donc jamais un enfant que vous auriez pu nourrir.

Le coût vient de la recherche. Chacun des n enfants parcourt les m biscuits, donc avec n = m = 5000, cela représente 25 millions de vérifications, ce qui est trop lent pour les tests les plus volumineux.

Algorithme

Triez les facteurs de gourmandise du plus petit au plus grand.
Gardez un indicateur pour chaque biscuit qui précise s'il est utilisé.
Pour chaque enfant, parcourez tous les biscuits et retenez le plus petit biscuit inutilisé dont la taille est au moins égale à la gourmandise de l'enfant.
Si vous en trouvez un, marquez-le comme utilisé et comptez l'enfant comme satisfait.
Renvoyez le nombre.

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

Trier les deux et utiliser deux pointeurs

Intuition

Le parcours ci-dessus recherche encore et encore le plus petit biscuit qui convient. Triez aussi les biscuits, et cette recherche disparaît : les biscuits sont classés par taille croissante, vous rencontrez donc d’abord le plus petit biscuit qui convient.

Parcourez les biscuits du plus petit au plus grand et gardez un pointeur, child, sur l’enfant le moins gourmand qui attend encore. Si le biscuit est au moins aussi grand que g[child], cet enfant est rassasié et le pointeur passe à l’enfant suivant. S’il est plus petit, il est aussi plus petit que tous les enfants qui attendent encore, puisqu’ils sont triés : le biscuit est donc inutile et vous passez au suivant.

Dans le premier exemple, les biscuits triés sont 1, 2, 3, 5 et les appétits triés sont 2, 4, 7. Le biscuit 1 est trop petit pour 2. Le biscuit 2 rassasie l’enfant qui en veut 2. Le biscuit 3 est trop petit pour 4. Le biscuit 5 rassasie l’enfant qui en veut 4. Le pointeur s’arrête à 2 : c’est la réponse.

Chaque pointeur ne se déplace que vers l’avant : le parcours est donc en O(n + m), et les deux tris dominent. Le tri en place ne nécessite pas de tableaux supplémentaires.

Algorithme

Triez g et s par ordre croissant.
Définissez child = 0, l’enfant le moins gourmand encore en attente.
Pour chaque biscuit, en commençant par le plus petit : si child est encore inférieur à la longueur de g et que le biscuit est au moins aussi grand que g[child], ajoutez 1 à child.
Retournez child, le nombre d’enfants nourris.

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

Pièges et cas limites

La plupart des mauvaises réponses viennent d’un appariement dans le mauvais ordre ou du déplacement du mauvais pointeur.

Donner à un enfant un biscuit plus gros que nécessaire. Avec g = [1, 2] et s = [1, 3], donner le biscuit 3 à l’enfant qui en veut 1 laisse l’enfant qui en veut 2 sur sa faim, alors que le bon appariement rassasie les deux.
Avancer le pointeur de l’enfant lorsqu’un biscuit est trop petit. L’enfant a toujours besoin d’un biscuit ; c’est le biscuit qui ne sert à rien.
Oublier de vérifier les limites du pointeur de l’enfant. Une fois que tous les enfants sont rassasiés, il ne faut pas lire les biscuits restants au-delà de la fin de g.
Comparer avec > au lieu de ≥. Un biscuit exactement de la taille du facteur de gourmandise suffit.
Trier les nombres comme du texte. En JavaScript, sort() sans comparateur place 10 avant 9.

Questions fréquentes4

Quelle est la complexité temporelle de Assign Cookies ?

Le tri des deux tableaux coûte O(n log n + m log m), et le parcours à deux pointeurs qui suit coûte O(n + m), donc ce sont les tris qui dominent. Le tri sur place maintient l’espace supplémentaire à O(1), hormis celui utilisé par le tri lui-même.

Pourquoi le choix glouton fonctionne-t-il pour Assign Cookies ?

Soit k le plus petit biscuit qui convient à l’enfant le moins gourmand. Supposons qu’une attribution optimale donne à cet enfant un autre biscuit. Échangeons-les : l’enfant prend k, et celui qui avait k prend l’autre biscuit, qui est au moins aussi grand que k, et reste donc rassasié. Le nombre ne change pas ; une attribution optimale peut donc toujours commencer par le choix glouton, et le même raisonnement se répète pour les enfants et les biscuits restants.

Peux-tu commencer par l’enfant le plus gourmand à la place ?

Oui. Triez les deux tableaux, puis parcourez-les en partant du plus gros biscuit et de l’enfant le plus gourmand : si le plus gros biscuit restant convient à l’enfant le plus gourmand restant, donnez-le-lui et avancez les deux pointeurs ; sinon, aucun biscuit ne peut satisfaire cet enfant, alors passez à l’enfant suivant. Cela donne le même nombre dans le même temps.

« Assign Cookies » est-il un problème de programmation dynamique ?

Non. Un argument d’échange montre que le choix glouton est toujours sûr, donc un tri suivi d’un seul parcours suffit, en O(n log n + m log m). Un tableau construit à partir des deux tableaux triés, comme un tableau de plus longue sous-séquence commune, trouve également la réponse, mais nécessite un temps de O(n × m) pour obtenir le même résultat.

Python

def findContentChildren(g, s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

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

Attendu