Insert Interval

Q: Quelle est la complexité temporelle de l’insertion d’un intervalle ?

La solution en un seul passage s’exécute en O(n) temps, puisque chaque intervalle est copié ou fusionné une seule fois, et utilise un espace de O(n) pour un résultat pouvant contenir jusqu’à n+1 intervalles. L’ajout de l’intervalle et le nouveau tri prennent O(n log n) .

Q: En quoi Insert Interval diffère-t-il de Merge Intervals ?

Merge Intervals part d’une liste non triée où chaque intervalle peut chevaucher n’importe quel autre, elle commence donc par la trier. Ici, la liste est triée et les anciens intervalles ne se touchent jamais, donc seul le nouvel intervalle peut déclencher une fusion, et les intervalles avec lesquels il fusionne forment une séquence continue. Un seul parcours suffit.

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

[a, b] et [c, d] ont un point en commun exactement lorsque a ≤ d et c ≤ b . Cela considère que les intervalles qui se touchent, comme [2, 4] et [4, 8] , se chevauchent, comme le veut ce problème. Pour que les intervalles qui se touchent restent séparés, utilisez a < d et c < b .

MoyenIntervalles

+10

Tu reçois des intervalles triés par début sous forme de deux tableaux : l’intervalle i est [starts[i], ends[i]], et aucun couple d’intervalles ne se chevauche ni ne se touche. Insère le nouvel intervalle [newStart, newEnd], fusionne-le avec chaque intervalle qu’il chevauche ou touche, puis renvoie tous les intervalles sous forme 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. [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, correspondant aux 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 début, et deux d'entre eux ne se chevauchent pas et ne se touchent pas.
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 deviennent donc [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, 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 ; il s’insère donc entre eux sans fusionner avec quoi que ce soit.

Pour aller plus loin

Si tu insères de nombreux intervalles les uns après les autres, comment les stockerais-tu pour que chaque insertion coûte O(log n) plus une étape par ancien intervalle qu’elle absorbe ?

Indices

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

0 sur 3 ouverts

Solution

Les anciens intervalles sont triés et disjoints, donc seul le nouvel intervalle peut provoquer une fusion. Cela divise la liste en trois groupes : les intervalles qui se terminent avant qu’il 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. Un seul parcours, sans tri.

Ajoute-le et fusionne à nouveau le tout

Intuition

Réutiliser la fusion d’intervalles : ajoute le nouvel intervalle, trie les n+1 intervalles par début et parcours-les en conservant le dernier intervalle fusionné. Après le tri, un intervalle ne peut chevaucher que le groupe qui le précède ; lorsque le début suivant est inférieur ou égal à la fin conservée, étends la fin ; sinon, un espace apparaît et un nouvel intervalle commence.

Le tri coûte O(n log n) pour remettre en ordre une liste qui est désordonnée à un seul endroit, et il ne tient pas compte du fait que les anciens intervalles ne fusionnent jamais entre eux.

Algorithme

Associez chaque début à sa fin et 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 passage en trois parties

Intuition

La liste est triée et ses intervalles sont disjoints ; les intervalles qui rencontrent le nouveau forment donc une suite ininterrompue. Tout ce qui précède cette suite vérifie ends[i] < newStart : ces intervalles se terminent avant le début du nouvel intervalle. Le test est strict, car un intervalle qui se termine exactement à newStart touche le nouveau et doit fusionner avec lui.

Dans la suite, un intervalle vérifiant starts[i] ≤ mergedEnd chevauche ou touche l’intervalle que vous construisez ; il l’élargit donc au plus petit début et à la plus grande fin. Le premier intervalle qui commence après mergedEnd met fin à la suite, puisque tous les suivants commencent encore plus à droite. Si la suite est vide, le nouvel intervalle est inséré tel quel. Dans le premier exemple, [1, 3] est recopié, [5, 7] et [10, 12] élargissent [6, 11] en [5, 12], et [15, 18] est recopié. Chaque intervalle est examiné une seule fois : temps O(n), sans mémoire supplémentaire au-delà du résultat.

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 continuez.
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

Inégalités incorrectes 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. Le premier test est strict, le second ne l’est pas.
Comparer avec mergedEnd + 1. Cela fusionne [1, 2] et [3, 4], qui n’ont aucun point en commun.
Conserver newStart comme début de l’intervalle fusionné. [6, 11] commence à l’intérieur de [5, 7], le résultat commence donc à 5.
Ajouter le nouvel intervalle uniquement lorsqu’il chevauche un autre intervalle. Lorsqu’il tombe dans un espace ou au-delà d’une des extrémités, comme c’est le cas de [5, 6], la boucle du milieu ne s’exécute jamais, mais il faut quand même l’ajouter.
Lire starts[i] avant de vérifier i < n. Un nouvel intervalle qui dépasse le dernier fait sortir l’index des limites du tableau.

Questions fréquentes3

Quelle est la complexité temporelle de l’insertion d’un intervalle ?

La solution en un seul passage s’exécute en O(n) temps, puisque chaque intervalle est copié ou fusionné une seule fois, et utilise un espace de O(n) pour un résultat pouvant contenir jusqu’à n+1 intervalles. L’ajout de l’intervalle et le nouveau tri prennent O(n log n).

En quoi Insert Interval diffère-t-il de Merge Intervals ?

Merge Intervals part d’une liste non triée où chaque intervalle peut chevaucher n’importe quel autre, elle commence donc par la trier. Ici, la liste est triée et les anciens intervalles ne se touchent jamais, donc seul le nouvel intervalle peut déclencher une fusion, et les intervalles avec lesquels il fusionne forment une séquence continue. Un seul parcours suffit.

Comment vérifier si deux intervalles se chevauchent ?

[a, b] et [c, d] ont un point en commun exactement lorsque a ≤ d et c ≤ b. Cela considère que les intervalles qui se touchent, comme [2, 4] et [4, 8], se chevauchent, comme le veut ce problème. Pour que les intervalles qui se touchent restent séparés, utilisez a < d et c < b.

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

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

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