Insert Interval

Q: Quelle est la complexité temporelle de Insert Interval ?

La solution en un seul parcours s’exécute en temps O(n) : chaque intervalle est copié ou fusionné exactement une fois. Le résultat contient jusqu’à n+1 intervalles, ce qui nécessite un espace de O(n) , et rien d’autre n’augmente avec la taille de l’entrée. Ajouter l’intervalle et effectuer un nouveau tri prend plutôt O(n log n) .

Q: En quoi Insert Interval est-il différent de Merge Intervals ?

Merge Intervals part d’une liste non triée où n’importe quel intervalle peut chevaucher n’importe quel autre ; il faut donc commencer par la trier. Dans Insert Interval, la liste est déjà triée et les anciens intervalles ne se touchent jamais, donc seul le nouvel intervalle peut déclencher une fusion. Les intervalles avec lesquels il fusionne forment une seule séquence continue, c’est pourquoi un seul parcours sans tri suffit.

Q: Comment vérifier si deux intervalles se chevauchent ?

Les intervalles [a, b] et [c, d] ont au moins un point en commun exactement lorsque a ≤ d et c ≤ b . Cela signifie que des intervalles qui se touchent, comme [2, 4] et [4, 8] , sont considérés comme se chevauchant, ce que demande ce problème. Si les intervalles qui se touchent devaient rester séparés, vous utiliseriez plutôt a < d et c < b .

Q: La recherche binaire peut-elle accélérer l’insertion d’un intervalle ?

La recherche binaire trouve où la séquence fusionnée commence et se termine en O(log n) , car les débuts et les fins sont tous deux triés. Cependant, la fonction renvoie toujours une nouvelle liste, et y copier les intervalles inchangés coûte O(n) . La complexité totale reste donc O(n) . La recherche binaire est avantageuse lorsque les intervalles se trouvent dans une structure qui peut supprimer et insérer une plage sans effectuer de copie, comme un arbre équilibré.

MoyenIntervalles

+10

Tu reçois une liste d’intervalles triés par début, sous la forme de deux tableaux de même longueur : l’intervalle i est [starts[i], ends[i]]. Aucun ne se chevauche ni ne se touche. Tu reçois également un nouvel intervalle, [newStart, newEnd]. Insère-le, fusionne-le avec chaque intervalle qu’il chevauche ou touche, puis renvoie tous les intervalles sous la forme d’un tableau à 2 dimensions de paires [start, end], triées par début.

Deux intervalles se touchent lorsque l’un se termine là où l’autre commence, comme [2, 4] et [4, 8], et les intervalles qui se touchent fusionnent en un seul. [1, 2] et [3, 4] n’ont aucun point en commun, ils restent donc séparés.

Fonction

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: le début de chaque intervalle, par ordre croissant
endsinteger-array: la fin de chaque intervalle, en faisant correspondre les débuts
newStartinteger: le début de l’intervalle à insérer
newEndinteger: la fin de l’intervalle à insérer
Renvoieinteger-2d-array: les intervalles après l’insertion sous forme de paires [start, end], triées par start

Contraintes

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1] : les intervalles sont triés par ordre de début, et aucun couple d’entre eux ne se chevauche ni ne se touche.
0 ≤ newStart ≤ newEnd ≤ 10⁵

Exemples

Entrée: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
Sortie: [[1, 3], [5, 12], [15, 18]]
Explication: [6, 11] chevauche [5, 7] et [10, 12], les trois fusionnent donc en [5, 12]. [1, 3] se termine avant 6 et [15, 18] commence après 12, donc les deux restent inchangés.

Entrée: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
Sortie: [[2, 9]]
Explication: [4, 8] touche [2, 4] en 4 et [8, 9] en 8. Le contact compte comme un chevauchement, donc les trois fusionnent en [2, 9].

Entrée: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
Sortie: [[1, 2], [5, 6], [9, 10]]
Explication: [5, 6] se trouve dans l’intervalle entre 2 et 9 et ne touche aucun des deux voisins, donc elle s’insère entre eux et rien ne fusionne.

+20 tests cachés à la soumission

Pour aller plus loin

Supposons que vous insériez de nombreux nouveaux intervalles, les uns après les autres, dans la même liste. Comment stockeriez-vous les intervalles pour que chaque insertion coûte O(log n), plus une étape pour chaque ancien intervalle qu’elle engloutit ?

Indices

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

0 sur 3 ouverts

Solution

Les anciens intervalles sont déjà séparés et ordonnés, donc seul le nouvel intervalle peut provoquer une fusion. Cela divise la liste en trois groupes : les intervalles qui se terminent avant que le nouvel intervalle commence, ceux qui le chevauchent ou le touchent, et ceux qui commencent après qu’il se termine. Copiez le premier groupe, fusionnez le groupe du milieu en un seul intervalle, puis copiez le dernier groupe. Un seul parcours, aucun tri.

Ajoutez-le et fusionnez à nouveau le tout

Intuition

Si tu as résolu Merge Intervals, tu peux réutiliser cette solution ici. Ajoute le nouvel intervalle à la liste, trie les n+1 intervalles par début, puis fusionne-les. Après le tri, un intervalle ne peut chevaucher que le groupe qui le précède, donc tu parcours la liste en gardant le dernier intervalle fusionné. Lorsque le début suivant est inférieur ou égal à sa fin, prolonge la fin. Sinon, il y a un véritable écart et un nouvel intervalle commence.

Applique cette méthode au premier exemple. La liste devient [1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] reste seul, car 5 est supérieur à 3. 6 est inférieur ou égal à 7, donc [5, 7] s’étend à [5, 11]. 10 est inférieur ou égal à 11, donc l’intervalle s’étend à [5, 12]. 15 est supérieur à 12, donc [15, 18] commence un nouvel intervalle.

C’est correct et, avec 2000 intervalles, l’exécution est rapide. Mais cette méthode ignore deux faits qui t’ont été fournis : la liste est déjà triée et les anciens intervalles ne se chevauchent jamais entre eux. Payer O(n log n) pour retrier une liste qui n’est désordonnée qu’à un seul endroit, c’est l’étape qu’un recruteur te demandera de supprimer.

Algorithme

Associez chaque début à sa fin, puis ajoutez [newStart, newEnd] à la liste.
Triez les intervalles par début.
Parcourez-les dans l’ordre en conservant le dernier intervalle fusionné.
Si le début suivant est inférieur ou égal à la fin conservée, remplacez cette dernière par la plus grande des deux fins.
Sinon, ajoutez l’intervalle suivant comme nouvel intervalle fusionné. Renvoyez la liste fusionnée.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

Un parcours en trois parties

Intuition

Parcourez la liste une fois avec un indice i et divisez-la en trois séquences. D’abord, chaque intervalle pour lequel ends[i] < newStart se termine avant que le nouvel intervalle ne commence, donc il ne partage aucun point avec lui : copiez-le dans le résultat. Le test utilise un < strict, car un intervalle qui se termine exactement à newStart touche le nouvel intervalle et doit être fusionné avec lui.

Ensuite, chaque intervalle pour lequel starts[i] ≤ mergedEnd chevauche ou touche l’intervalle que vous êtes en train de construire. Intégrez-le : mergedStart devient le plus petit début et mergedEnd la plus grande fin. Les intervalles de cette séquence sont côte à côte, car la liste est triée. Dès qu’un intervalle commence après mergedEnd, tous les suivants commencent encore plus à droite, donc aucun intervalle au-delà ne peut être fusionné. Ajoutez l’intervalle fusionné ; cette étape couvre également le cas où la séquence est vide et où le nouvel intervalle est ajouté seul.

Enfin, copiez tout ce qui reste. Ces intervalles commencent après la fin de l’intervalle fusionné, et ils étaient déjà séparés les uns des autres.

Suivez le premier exemple. [1, 3] se termine avant 6 : copiez-le. [5, 7] commence à 5, qui est inférieur ou égal à 11 : l’intervalle fusionné devient [5, 11]. [10, 12] commence à 10, inférieur ou égal à 11 : il devient [5, 12]. [15, 18] commence après 12, alors ajoutez [5, 12] et copiez [15, 18]. Chaque intervalle est examiné une seule fois, donc le temps d’exécution est O(n), et la seule mémoire supplémentaire est celle du résultat lui-même.

Algorithme

Copiez les intervalles dans le résultat tant que ends[i] < newStart.
Définissez mergedStart = newStart et mergedEnd = newEnd.
Tant que starts[i] ≤ mergedEnd, définissez mergedStart sur le plus petit début et mergedEnd sur la plus grande fin, puis passez à la suite.
Ajoutez [mergedStart, mergedEnd].
Copiez les intervalles restants et renvoyez le résultat.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

Pièges et cas limites

La boucle est courte, donc la plupart des bogues proviennent d’une comparaison incorrecte ou d’un cas oublié aux extrémités de la liste.

Utiliser la mauvaise inégalité pour les intervalles qui se touchent. Avec ends[i] ≤ newStart dans la première boucle, ou starts[i] < mergedEnd dans la deuxième, [2, 4] et [4, 8] restent séparés. Les intervalles qui se touchent fusionnent : le premier test est donc strict, et le deuxième ne l’est pas.
Fusionner des intervalles qui semblent seulement adjacents. [1, 2] et [3, 4] n’ont aucun point en commun ; comparer avec mergedEnd + 1 réunit donc des intervalles qui devraient rester séparés.
Conserver newStart comme début de l’intervalle fusionné. Lorsque le nouvel intervalle commence à l’intérieur d’un ancien, comme [6, 11] à l’intérieur de [5, 7], le résultat commence à 5. Prends le plus petit des deux débuts.
Ajouter le nouvel intervalle uniquement lorsqu’il chevauche un autre intervalle. S’il se trouve avant tous les intervalles, après tous les intervalles ou dans un espace entre eux, la boucle du milieu ne s’exécute jamais, et le nouvel intervalle doit quand même être ajouté.
Lire starts[i] ou ends[i] avant de vérifier i < n. Lorsque le nouvel intervalle dépasse le dernier intervalle, l’indice sort des limites des tableaux.

Questions fréquentes4

Quelle est la complexité temporelle de Insert Interval ?

La solution en un seul parcours s’exécute en temps O(n) : chaque intervalle est copié ou fusionné exactement une fois. Le résultat contient jusqu’à n+1 intervalles, ce qui nécessite un espace de O(n), et rien d’autre n’augmente avec la taille de l’entrée. Ajouter l’intervalle et effectuer un nouveau tri prend plutôt O(n log n).

En quoi Insert Interval est-il différent de Merge Intervals ?

Merge Intervals part d’une liste non triée où n’importe quel intervalle peut chevaucher n’importe quel autre ; il faut donc commencer par la trier. Dans Insert Interval, la liste est déjà triée et les anciens intervalles ne se touchent jamais, donc seul le nouvel intervalle peut déclencher une fusion. Les intervalles avec lesquels il fusionne forment une seule séquence continue, c’est pourquoi un seul parcours sans tri suffit.

Comment vérifier si deux intervalles se chevauchent ?

Les intervalles [a, b] et [c, d] ont au moins un point en commun exactement lorsque a ≤ d et c ≤ b. Cela signifie que des intervalles qui se touchent, comme [2, 4] et [4, 8], sont considérés comme se chevauchant, ce que demande ce problème. Si les intervalles qui se touchent devaient rester séparés, vous utiliseriez plutôt a < d et c < b.

La recherche binaire peut-elle accélérer l’insertion d’un intervalle ?

La recherche binaire trouve où la séquence fusionnée commence et se termine en O(log n), car les débuts et les fins sont tous deux triés. Cependant, la fonction renvoie toujours une nouvelle liste, et y copier les intervalles inchangés coûte O(n). La complexité totale reste donc O(n). La recherche binaire est avantageuse lorsque les intervalles se trouvent dans une structure qui peut supprimer et insérer une plage sans effectuer de copie, comme un arbre équilibré.

Python

def insertInterval(starts, ends, newStart, newEnd):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

Attendu

[[1, 3], [5, 12], [15, 18]]