Non-overlapping Intervals

Q: Quelle est la complexité temporelle de Non-overlapping Intervals ?

La solution gloutonne trie les intervalles par fin en O(n log n) , puis les parcourt une seule fois en O(n) , donc la complexité totale est O(n log n) . La copie triée des intervalles utilise un espace de O(n) . La version de programmation dynamique est en O(n²) , et essayer chaque ensemble à conserver est en O(2^n) .

MoyenIntervalles Glouton

+10

Vous obtenez une liste d’intervalles sous forme de deux tableaux : l’intervalle i va de starts[i] à ends[i]. Supprimez le moins d’intervalles possible afin qu’aucun des intervalles restants ne se chevauche. Deux intervalles qui se touchent seulement, lorsque l’un se termine exactement au point où l’autre commence, ne se chevauchent pas.

Écrivez une fonction nommée eraseOverlapIntervals qui renvoie le nombre minimal d’intervalles à supprimer.

Fonction

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: le début de chaque intervalle
endsinteger-array: la fin de chaque intervalle, au même indice que son début
Renvoieinteger: le nombre minimal d’intervalles à supprimer pour que les autres ne se chevauchent pas

Contraintes

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
Les intervalles ne sont pas triés. Deux intervalles peuvent être identiques.

Exemples

Entrée: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
Sortie: 2
Explication: Dans l’ordre de début, les intervalles sont [1,4], [2,3], [3,6] et [5,7]. Gardez [2,3] et [3,6], qui se touchent seulement, et supprimez les 2 autres. Vous ne pouvez pas en garder trois : [1,4] chevauche [2,3] et [3,6] chevauche [5,7], et n’importe quels trois des quatre contiennent l’une de ces paires.

Entrée: starts = [0, 0, 0]ends = [5, 5, 5]
Sortie: 2
Explication: Les trois intervalles sont tous [0,5], donc deux quelconques d’entre eux se chevauchent. Un seul peut être conservé, et tu supprimes les autres 2.

Entrée: starts = [4, 1, 2]ends = [6, 2, 4]
Sortie: 0
Explication: [1,2], [2,4] et [4,6] se rejoignent en début et en fin sans jamais se chevaucher ; vous ne supprimez donc rien et la réponse est 0.

+17 tests cachés à la soumission

Pour aller plus loin

Supposons que chaque intervalle ait aussi une valeur et que tu veuilles obtenir la valeur totale la plus élevée parmi les intervalles qui ne se chevauchent pas. Garder l’intervalle qui se termine en premier fonctionne-t-il toujours ? Qu’utiliserais-tu à la place ?

Solution

Supprimer le moins d’intervalles possible revient à conserver le plus grand nombre d’intervalles qui ne se chevauchent pas ; la réponse est donc n moins la taille de cet ensemble maximal. Essayer tous les ensembles à conserver nécessite un temps exponentiel, et la programmation dynamique sur des chaînes d’intervalles ramène la complexité à O(n²). Une règle gloutonne suffit pour terminer en O(n log n) : parmi les intervalles qui s’ajustent encore, conserve toujours celui qui se termine le plus tôt.

Conserver ou supprimer chaque intervalle

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Inversez la question. Supprimer le moins d’intervalles possible signifie conserver le plus grand nombre d’intervalles qui ne se chevauchent pas, et la réponse est n moins ce nombre. Cherchez donc le plus grand ensemble que vous pouvez conserver.

Triez les intervalles par début et décidez pour chacun, dans cet ordre, s’il faut le supprimer ou le conserver. Vous ne pouvez le conserver que s’il commence à la fin du dernier intervalle conservé ou après. Cette simple vérification suffit : les intervalles conservés forment alors une chaîne dans laquelle chacun commence à la fin du précédent ou après, donc aucun ne se chevauche. Essayez les deux choix pour chaque intervalle et retenez le meilleur résultat.

Dans le premier exemple, les intervalles triés sont [1,4], [2,3], [3,6], [5,7]. Conserver [1,4] bloque [2,3] et [3,6], qui commencent avant 4, et laisse de la place pour [5,7] : 2 intervalles conservés. Supprimer [1,4] et conserver [2,3], puis [3,6], en conserve également 2. Aucune branche n’atteint 3, donc vous supprimez 4-2 = 2.

Chaque intervalle peut doubler le nombre de branches ; n intervalles peuvent donc entraîner jusqu’à 2^n chemins. Trente intervalles qui ne se chevauchent pas représentent déjà plus d’un milliard d’appels, et les tests vont jusqu’à 5000 intervalles. La récursion atteint aussi une profondeur de n niveaux : 5000 appels pour les tests les plus grands, ce qui dépasse la limite par défaut de Python, fixée à 1,000.

Algorithme

Triez les intervalles par ordre de début, en gardant chaque début associé à sa propre fin.
Définissez mostKept(i, last) : le nombre maximal d’intervalles que vous pouvez conserver à partir de la position i, lorsque last est la position du dernier intervalle conservé (-1 s’il n’y en a aucun).
Lorsque vous dépassez la fin de la liste, renvoyez 0. Sinon, commencez par mostKept(i+1, last), le résultat obtenu en supprimant l’intervalle i.
Si l’intervalle i commence à la fin de l’intervalle last ou après, essayez également 1 + mostKept(i+1, i) et conservez le résultat le plus élevé.
Renvoyez n moins mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

Chaîne la plus longue avec la programmation dynamique

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La recherche ci-dessus répond encore et encore à la même question : quelle est la chaîne la plus longue qui se termine par cet intervalle ? Stocke cette réponse une fois par intervalle. Trie par début, et soit chain[i] le nombre maximal d’intervalles que tu peux conserver lorsque l’intervalle i est le dernier conservé.

L’intervalle conservé juste avant i doit se terminer au plus tard à starts[i]. Tous ces intervalles apparaissent plus tôt dans l’ordre trié : un intervalle commence avant de se terminer, donc il commence avant starts[i]. On obtient ainsi chain[i] = 1 + chain[j] pour le meilleur j antérieur tel que ends[j] ≤ starts[i], ou 1 si aucun intervalle ne convient. La plus grande valeur de chain correspond au nombre maximal d’intervalles que tu peux conserver.

Pour le premier exemple, trié ainsi : [1,4], [2,3], [3,6], [5,7], les valeurs sont 1, 1, 2 et 2 : [3,6] peut suivre [2,3], et [5,7] peut suivre [1,4] ou [2,3]. La chaîne la plus longue est de longueur 2, donc tu supprimes 4-2 = 2.

Chaque intervalle examine tous les intervalles qui le précèdent, soit n(n-1)/2 vérifications. Avec n = 5000, cela représente environ 12,5 millions de vérifications : acceptable dans un langage compilé, trop lent dans les langages plus lents pour les tests les plus volumineux, et bien moins performant que l’algorithme glouton ci-dessous.

Algorithme

Trie les intervalles par point de départ, en conservant chaque point de départ avec sa propre fin.
Définis chain[i] = 1 pour chaque intervalle.
Pour chaque i et chaque j < i tel que ends[j] ≤ starts[i], définis chain[i] comme chain[j]+1 si cette valeur est supérieure.
Renvoie n moins la plus grande valeur de chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

Algorithme glouton : conserver l’intervalle qui se termine en premier

Intuition

Regarde l’intervalle qui a la plus petite fin. Une solution optimale le garde toujours. Prends n’importe quel plus grand ensemble d’intervalles que tu peux garder et remplace son intervalle le plus tôt par celui-ci. Le nouvel intervalle se termine au plus tard à la fin de celui qu’il remplace, donc il se termine toujours au plus tard au début du prochain intervalle conservé. L’ensemble reste sans chevauchements et conserve la même taille : garder l’intervalle qui se termine le plus tôt ne te coûte donc rien.

Une fois que tu l’as gardé, tous les intervalles qui commencent avant sa fin le chevauchent et doivent être supprimés. Il reste la même question pour les intervalles qui commencent à cette fin ou après : applique donc à nouveau la même règle. En pratique : trie par fin, parcours la liste et mémorise lastEnd, la fin du dernier intervalle conservé. Garde un intervalle qui commence à lastEnd ou après ; compte tout autre intervalle comme supprimé.

Le premier exemple, trié par fin, donne [2,3], [1,4], [3,6], [5,7]. Garde [2,3], donc lastEnd = 3. [1,4] commence à 1, avant 3 : supprime-le. [3,6] commence à 3, pas avant 3 : garde-le, lastEnd = 6. [5,7] commence à 5, avant 6 : supprime-le. Deux intervalles supprimés.

D’autres critères semblent tentants, mais échouent. En triant par début, on garde [0,100] alors qu’il englobe [1,2], [3,4] et [5,6], ce qui entraîne la suppression de trois intervalles au lieu d’un. Garder l’intervalle le plus court échoue avec [1,5], [4,7], [6,10] : le court [4,7] chevauche les deux autres, donc le garder entraîne deux suppressions alors qu’une seule suffit. La fin est le critère qui laisse le plus de place à tout ce qui vient après.

Le tri coûte O(n log n) et le parcours O(n). La copie triée des intervalles occupe un espace de O(n).

Algorithme

Trie les intervalles par ordre de fin, en gardant chaque fin associée à son propre début.
Conserve le premier intervalle : définis lastEnd à sa fin et removed à 0.
Pour chaque intervalle suivant, s’il commence à lastEnd ou après, conserve-le et définis lastEnd à sa fin.
Sinon, ajoute 1 à removed.
Renvoie removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

Pièges et cas limites

La plupart des mauvaises réponses viennent de la clé de tri ou de la comparaison lorsque deux intervalles se touchent.

Considérer que les intervalles qui se touchent se chevauchent. Avec start > lastEnd au lieu de start ≥ lastEnd, la chaîne [1,2], [2,4], [4,6] perd [2,4], qui commence exactement là où [1,2] se termine, et la réponse est 1 au lieu de 0.
Trier par début et toujours garder l’intervalle qui commence le plus tôt en cas de chevauchement. Un intervalle large [0,100] écarte alors [1,2], [3,4] et [5,6]. Si tu tries par début, garde celui des deux intervalles qui se chevauchent qui se termine en premier.
Comparer chaque intervalle à son voisin dans la liste triée au lieu de le comparer au dernier intervalle conservé. Après avoir retiré [1,4], l’intervalle suivant doit être comparé à la fin de [2,3], et non à 4.
Trier starts et ends dans deux listes distinctes. Chaque fin doit rester associée à son début, sinon tu compares un début à la fin d’un autre intervalle.
Renvoyer le nombre d’intervalles que tu conserves. La question demande le nombre d’intervalles retirés, soit n moins ce nombre.

Questions fréquentes4

Quelle est la complexité temporelle de Non-overlapping Intervals ?

La solution gloutonne trie les intervalles par fin en O(n log n), puis les parcourt une seule fois en O(n), donc la complexité totale est O(n log n). La copie triée des intervalles utilise un espace de O(n). La version de programmation dynamique est en O(n²), et essayer chaque ensemble à conserver est en O(2^n).

Pourquoi le tri par heure de fin donne-t-il le moins de suppressions ?

L’intervalle qui se termine en premier peut remplacer le premier intervalle de toute solution optimale sans créer de chevauchement, car il ne se termine pas plus tard. Ainsi, une solution optimale le conserve, et après avoir supprimé tout ce qui le chevauche, le problème restant est le même sur un ensemble plus petit. En répétant ce raisonnement, on montre que chaque choix glouton est sûr.

Peux-tu plutôt trier par heure de début ?

Oui, avec une règle différente en cas de chevauchement. Parcourez les intervalles par ordre de début et, lorsque le suivant chevauche le dernier intervalle conservé, comptez une suppression et gardez celui des deux qui se termine le plus tôt. Cette méthode supprime le même nombre d’intervalles que le tri par fin et s’exécute dans le même temps O(n log n).

Le problème des intervalles sans chevauchement est-il identique au problème de sélection d’activités ?

C’est l’autre facette du problème. La sélection d’activités consiste à trouver le plus grand nombre d’intervalles qui ne se chevauchent pas ; ce problème consiste à en supprimer le moins possible, soit n moins ce nombre. La même règle gloutonne, garder l’activité qui se termine en premier, résout les deux problèmes.

Python

def eraseOverlapIntervals(starts, ends):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

starts = [3, 1, 5, 2]
ends = [6, 4, 7, 3]

Attendu

Non-overlapping Intervals

Fonction

Contraintes

Exemples

Indices

Solution

Conserver ou supprimer chaque intervalle

Chaîne la plus longue avec la programmation dynamique

Algorithme glouton : conserver l’intervalle qui se termine en premier

Pièges et cas limites

Questions fréquentes4

Problèmes similaires