Non-overlapping Intervals

Q: Quelle est la complexité temporelle des intervalles sans chevauchement ?

La solution gloutonne trie selon les fins en O(n log n) et parcourt les intervalles une seule fois ; le total est donc de O(n log n) , avec un espace de O(n) pour la copie triée. La version à programmation dynamique est en O(n²) , et essayer chaque ensemble à conserver est en O(2^n) .

MoyenIntervalles Glouton

+10

L’intervalle i va de starts[i] à ends[i]. Retournez le plus petit nombre d’intervalles que vous devez supprimer afin qu’aucun des intervalles restants ne se chevauche. Deux intervalles qui se touchent uniquement, lorsque l’un se termine exactement au point où l’autre commence, ne se chevauchent pas.

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 plus petit nombre 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. Trois intervalles ne peuvent pas être conservés : [1,4] chevauche [2,3], et [3,6] chevauche [5,7].

Entrée: starts = [0, 0, 0]ends = [5, 5, 5]
Sortie: 2
Explication: Les trois intervalles sont [0,5], donc deux quelconques se chevauchent. L’un reste et tu supprimes 2.

Entrée: starts = [4, 1, 2]ends = [6, 2, 4]
Sortie: 0
Explication: [1,2], [2,4] et [4,6] se rejoignent bout à bout sans jamais se chevaucher, donc tu ne supprimes rien et la réponse est 0.

Pour aller plus loin

Supposons que chaque intervalle ait une valeur et que tu veuilles obtenir la valeur totale maximale parmi les intervalles qui ne se chevauchent pas. Choisir l’intervalle qui se termine le plus tôt fonctionne-t-il toujours ?

Solution

Supprimer le moins d’intervalles possible revient à conserver le plus grand nombre d’intervalles qui ne se chevauchent pas : la réponse est n moins ce nombre. Une règle gloutonne permet de trouver ce nombre en O(n log n) : parmi les intervalles qui tiennent 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

Triez les intervalles par début et décidez pour chacun de le garder ou de le supprimer. Vous ne pouvez le garder que s’il commence à la fin du dernier intervalle conservé ou après, afin que les intervalles conservés forment une chaîne sans chevauchement. Essayez les deux choix pour chaque intervalle et gardez le plus grand nombre ; la réponse est n moins ce nombre.

Chaque intervalle peut doubler le nombre de branches, donc n intervalles peuvent mener à jusqu’à 2^n chemins. Trente intervalles qui ne se chevauchent pas représentent déjà plus d’un milliard d’appels, et n peut aller jusqu’à 5000.

Algorithme

Trie les intervalles par début, en conservant chaque début avec sa propre fin.
Définis mostKept(i, last) : le nombre maximal d’intervalles que tu peux conserver à partir de la position i, lorsque last est le dernier intervalle conservé (-1 s’il n’y en a aucun).
Au-delà de la fin, renvoie 0. Sinon, prends mostKept(i+1, last), ce qui supprime l’intervalle i.
Si l’intervalle i commence à la fin de last ou après, essaie aussi 1 + mostKept(i+1, i) et conserve la plus grande valeur.
Renvoie 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)

La plus longue chaîne avec la programmation dynamique

Correcte, mais ne termine pas sur les plus gros tests

Intuition

La recherche pose toujours la même question : quelle est la longueur de la chaîne la plus longue qui se termine par cet intervalle ? Réponds-y une fois par intervalle. Trie les intervalles par début et définis chain[i] comme le nombre maximal d’intervalles que tu peux conserver avec l’intervalle i en dernier.

Un intervalle qui peut précéder directement i se termine au plus tard à starts[i] ; il commence donc plus tôt et se trouve avant dans l’ordre trié. On obtient ainsi chain[i] = 1 + chain[j] pour le meilleur j correspondant, ou 1 si aucun ne convient. Dans le premier exemple, les valeurs sont 1, 1, 2 et 2 ; tu conserves donc 2 intervalles et en supprimes 2.

La double boucle effectue n(n-1)/2 vérifications : environ 12,5 millions pour n = 5000.

Algorithme

Trie les intervalles par début, en gardant chaque début associé à 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] à chain[j]+1 lorsque cette valeur est supérieure.
Retourne 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)

Glouton : conserver l’intervalle qui se termine le plus tôt

Intuition

Choisis l’intervalle dont la fin est la plus petite. Il existe une solution optimale qui le conserve : dans tout ensemble de taille maximale que tu peux conserver, remplace le premier intervalle par celui-ci. Il se termine au plus tard, donc il se termine toujours avant ou au moment où commence l’intervalle conservé suivant, et l’ensemble garde la même taille sans chevauchements. Tous les intervalles qui commencent avant sa fin le chevauchent et doivent être retirés ; les intervalles restants, qui commencent à cette fin ou après, forment le même problème.

Dans le premier exemple, en triant par fin, tu conserves [2,3], tu retires [1,4], tu conserves [3,6] et tu retires [5,7]. Conserver plutôt l’intervalle le plus court échoue avec [1,5], [4,7], [6,10] : [4,7] chevauche les deux autres et entraîne deux suppressions, alors qu’une seule suffit.

Le tri coûte O(n log n) et le parcours O(n).

Algorithme

Triez les intervalles par ordre de fin, en conservant chaque fin avec son début.
Conservez le premier intervalle : définissez lastEnd sur sa fin et removed sur 0.
Pour chaque intervalle suivant, s’il commence à lastEnd ou après, conservez-le et définissez lastEnd sur sa fin.
Sinon, ajoutez 1 à removed.
Renvoyez 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

Considérer que des intervalles qui se touchent se chevauchent. Avec start > lastEnd au lieu de start ≥ lastEnd, la chaîne [1,2], [2,4], [4,6] donne 1 au lieu de 0.
Trier par début et conserver l’intervalle précédent en cas de chevauchement. Un intervalle large [0,100] écarte alors [1,2], [3,4] et [5,6] : trois suppressions au lieu d’une.
Comparer chaque intervalle à son voisin dans la liste triée au lieu de le comparer au dernier intervalle conservé. Dans le premier exemple, [3,6] doit être comparé à la fin de [2,3], et non à celle de l’intervalle supprimé [1,4], sinon la réponse est 3.
Trier starts et ends dans deux listes distinctes. Chaque fin doit rester associée à son propre début.
Renvoyer le nombre d’intervalles conservés plutôt que le nombre d’intervalles supprimés.

Questions fréquentes3

Quelle est la complexité temporelle des intervalles sans chevauchement ?

La solution gloutonne trie selon les fins en O(n log n) et parcourt les intervalles une seule fois ; le total est donc de O(n log n), avec un espace de O(n) pour la copie triée. La version à programmation dynamique est en O(n²), et essayer chaque ensemble à conserver est en O(2^n).

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 conservez celui des deux qui se termine en premier. On obtient le même nombre en 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 à choisir le plus grand nombre d’intervalles qui ne se chevauchent pas ; ce problème demande de supprimer le moins d’intervalles 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.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

Non-overlapping Intervals

Fonction

Contraintes

Exemples

Indices

Solution

Conserver ou supprimer chaque intervalle

La plus longue chaîne avec la programmation dynamique

Glouton : conserver l’intervalle qui se termine le plus tôt

Pièges et cas limites

Questions fréquentes3

Problèmes similaires