Chocolate Distribution Problem

Q: Quelle est la complexité temporelle du problème de distribution de chocolats ?

Le tri prend O(n log n) et le déplacement de la fenêtre de m paquets prend O(n) , donc le temps total est O(n log n) . L’espace supplémentaire est de O(n) pour une copie triée, ou de O(1) en plus du tri lui-même si tu tries l’entrée sur place.

Q: Le problème de la distribution de chocolat est-il un problème de fenêtre glissante ?

Oui, une fenêtre de taille fixe sur les paquets triés. Contrairement à une fenêtre à somme glissante, il n’y a rien à mettre à jour lorsqu’elle se déplace : la différence de chaque fenêtre s’obtient en soustrayant le premier paquet du dernier.

Q: Le problème de la distribution de chocolat peut-il être résolu sans tri ?

Les tailles ici sont au plus de 10^5 , donc un tri par comptage les ordonne en O(n + 10^5) et le même argument s’applique. Avec des tailles non bornées, les comparaisons seules ne peuvent pas faire mieux que O(n log n) : avec m = 2 , la réponse est 0 exactement lorsque deux paquets sont égaux, et détecter un doublon nécessite autant de comparaisons dans le pire des cas.

FacileTri Fenêtre glissante

+10

Tu as plusieurs paquets de chocolat, et packets[i] correspond au nombre de chocolats dans le paquet i. Chacun des m élèves reçoit exactement un paquet, donc m paquets différents sont distribués. Choisis-les de sorte que la différence entre le paquet le plus grand et le plus petit distribués soit aussi petite que possible.

Écris une fonction nommée minDifference qui renvoie cette différence minimale possible.

Fonction

minDifference(packets: integer-array, m: integer) → integer

packetsinteger-array: le nombre de chocolats dans chaque paquet
minteger: le nombre d’élèves, chacun recevant un paquet
Renvoieinteger: la plus petite différence possible entre le plus grand et le plus petit paquet distribué

Contraintes

2 ≤ m ≤ packets.length ≤ 10⁴
1 ≤ packets[i] ≤ 10⁵
Deux paquets peuvent contenir le même nombre de chocolats.

Exemples

Entrée: packets = [9, 3, 15, 7, 11, 4]m = 3
Sortie: 4
Explication: Une fois triés, les paquets sont 3, 4, 7, 9, 11 et 15. Les groupes 3, 4, 7 et 7, 9, 11 ont tous deux une différence de 4, et aucun groupe de trois paquets n’est plus rapproché.

Entrée: packets = [8, 1, 5]m = 3
Sortie: 7
Explication: Il y a trois élèves et trois paquets, donc chaque paquet est distribué et la différence est 8 - 1 = 7.

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Essayer chaque groupe de m paquets est beaucoup trop lent. Le meilleur choix consiste toujours en m paquets consécutifs une fois les paquets triés. Il suffit donc de trier une fois, puis la réponse est la plus petite différence parmi toutes les fenêtres de m paquets voisins, trouvée en un seul passage.

Répare le plus petit paquet

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Fixez le plus petit paquet que vous distribuez, low. Pour que le plus grand reste petit, prenez les m-1 plus petits paquets qui contiennent au moins low. La différence est alors le m-ième plus petit paquet contenant au moins low, moins low. Essayez chaque paquet comme low, ignorez ceux pour lesquels il y a moins de m paquets égaux ou supérieurs, et conservez la plus petite différence.

Chacun des n choix filtre et trie jusqu'à n paquets : O(n² log n). Avec n = 10^4 tailles différentes, les tris à eux seuls entraînent environ 6 × 10^8 comparaisons.

Algorithme

Initialisez best à une valeur qu’aucune réponse ne peut dépasser.
Pour chaque paquet low, récupérez tous les paquets contenant au moins low chocolats et triez-les.
S’il y en a au moins m, le m-ième plus petit moins low est un candidat.
Conservez le plus petit candidat dans best et renvoyez-le.

def minDifference(packets, m):
    best = max(packets) - min(packets)  # no gap can be wider than this
    for low in packets:
        # The packets that could go out alongside low, smallest first (low is one of them).
        bigger = sorted(x for x in packets if x >= low)
        if len(bigger) >= m:
            best = min(best, bigger[m - 1] - low)
    return best

Trier et faire glisser une fenêtre de m paquets

Intuition

Dans l’ordre trié, une fenêtre sizes[i..i+m-1] a son plus petit paquet en premier et son plus grand en dernier, donc sa différence est sizes[i+m-1] - sizes[i].

Un meilleur choix peut toujours être une fenêtre. Si un choix omet un paquet situé entre son plus petit et son plus grand, remplacez le plus grand par ce paquet. Le plus petit reste le même et le plus grand ne peut que diminuer, donc la différence n’augmente jamais. Répétez jusqu’à ce qu’il ne reste aucun écart.

Dans le premier exemple, les fenêtres de trois donnent 4, 5, 4 et 6 ; la réponse est donc 4. Le tri coûte O(n log n) et le parcours par fenêtre glissante O(n).

Algorithme

Trie les paquets par ordre croissant dans sizes.
Définis best à sizes[m-1] - sizes[0], la première fenêtre.
Pour chaque indice de départ i de 1 à n-m, compare sizes[i+m-1] - sizes[i] à best et conserve la plus petite valeur.
Renvoie best.

def minDifference(packets, m):
    sizes = sorted(packets)
    best = sizes[m - 1] - sizes[0]
    # The window sizes[i..i+m-1] holds m packets; its first is the smallest, its last the largest.
    for i in range(1, len(sizes) - m + 1):
        best = min(best, sizes[i + m - 1] - sizes[i])
    return best

Pièges et cas limites

Terminer la fenêtre à i+m au lieu de i+m-1, ce qui mesure m+1 paquets.
S’arrêter une fenêtre trop tôt. Les indices de départ vont de 0 à n-m inclus. Pour [1, 10, 20, 21] avec m = 2, une boucle avec i < n-m manque la seule différence de 1.
Ne pas trier. Dans [9, 3, 15, 7, 11, 4], les trois premiers paquets ont une différence de 12, alors que la réponse est 4.
Ne mesurer que la première fenêtre. Les m paquets les plus petits constituent un choix, mais le meilleur groupe peut commencer n’importe où.
Trier les nombres comme du texte. En JavaScript, sort() sans comparateur place 100000 avant 9.

Questions fréquentes3

Quelle est la complexité temporelle du problème de distribution de chocolats ?

Le tri prend O(n log n) et le déplacement de la fenêtre de m paquets prend O(n), donc le temps total est O(n log n). L’espace supplémentaire est de O(n) pour une copie triée, ou de O(1) en plus du tri lui-même si tu tries l’entrée sur place.

Le problème de la distribution de chocolat est-il un problème de fenêtre glissante ?

Oui, une fenêtre de taille fixe sur les paquets triés. Contrairement à une fenêtre à somme glissante, il n’y a rien à mettre à jour lorsqu’elle se déplace : la différence de chaque fenêtre s’obtient en soustrayant le premier paquet du dernier.

Le problème de la distribution de chocolat peut-il être résolu sans tri ?

Les tailles ici sont au plus de 10^5, donc un tri par comptage les ordonne en O(n + 10^5) et le même argument s’applique. Avec des tailles non bornées, les comparaisons seules ne peuvent pas faire mieux que O(n log n) : avec m = 2, la réponse est 0 exactement lorsque deux paquets sont égaux, et détecter un doublon nécessite autant de comparaisons dans le pire des cas.

def minDifference(packets, m):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

packets = [9, 3, 15, 7, 11, 4]
m = 3

Résultat attendu