Merge Intervals

Q: Quelle est la complexité temporelle de Merge Intervals ?

La solution par tri et balayage s’exécute en O(n log n) pour n intervalles : le tri coûte O(n log n) et le balayage O(n). Elle utilise O(n) d’espace supplémentaire pour les paires triées et le résultat.

Q: Pourquoi trier les intervalles par début et non par fin ?

Trié par début, un intervalle ne peut chevaucher que le groupe que tu es en train de construire ; une seule comparaison avec la fin de ce groupe suffit donc à tout décider. Trié par fin, un intervalle ultérieur peut commencer avant des groupes que tu as déjà clôturés : [5, 6] vient avant [1, 10] , et un balayage vers l’avant conserverait à tort 5 comme début.

Q: Peux-tu fusionner les intervalles sans espace supplémentaire ?

Oui, si tu peux modifier l’entrée. Trie les intervalles sur place, puis écris chaque intervalle fusionné au début du même tableau et conserve l’indice du dernier intervalle écrit. La complexité temporelle reste O(n log n), et le seul espace supplémentaire utilisé est celui nécessaire au tri dans ton langage.

MoyenIntervalles Tri

+10

Tu reçois un ensemble d’intervalles, chacun étant une plage de nombres entiers allant d’un début à une fin. Fusionne chaque groupe d’intervalles qui se chevauchent en un seul intervalle couvrant tout le groupe, puis renvoie les intervalles fusionnés triés par début. Les intervalles qui se touchent seulement, comme [1, 4] et [4, 5], sont considérés comme se chevauchant.

Les intervalles sont fournis sous forme de deux tableaux de même longueur : l’intervalle i est [starts[i], ends[i]]. Tu renvoies un tableau à 2 dimensions, une liste de paires [start, end].

Fonction

mergeIntervals(starts: integer-array, ends: integer-array) → integer-2d-array

startsinteger-array: le début de chaque intervalle
endsinteger-array: la fin de chaque intervalle, au même indice que son début
Renvoieinteger-2d-array: les intervalles fusionnés sous forme de paires [start, end], triées par valeur de début

Contraintes

1 ≤ starts.length == ends.length ≤ 10⁴
0 ≤ starts[i] ≤ ends[i] ≤ 10⁴
Les intervalles arrivent dans n’importe quel ordre.
Les intervalles qui ne se touchent qu’à une extrémité sont considérés comme se chevauchant.

Exemples

Entrée: starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
Sortie: [[1, 7], [12, 14]]
Explication: Dans l’ordre de début, [1, 4] chevauche [3, 6], qui chevauche [5, 7] ; les trois fusionnent donc en [1, 7]. [12, 14] commence après 7 et reste à part.

Pour aller plus loin

Les intervalles sont déjà fusionnés et triés par ordre de début, et vous devez ajouter un nouvel intervalle. Pouvez-vous renvoyer la liste fusionnée en O(n), sans la trier à nouveau ?

Solution

La fusion de paires dans n’importe quel ordre nécessite plusieurs parcours, car chaque fusion élargit un intervalle et lui permet d’atteindre des intervalles que vous avez déjà vérifiés. Triez plutôt par début. Ainsi, un intervalle ne peut chevaucher que le groupe que vous êtes en train de construire, et un seul parcours suffit.

Fusionnez les paires qui se chevauchent jusqu’à ce que plus rien ne change

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Les intervalles [a, b] et [c, d] se chevauchent lorsque c ≤ b et a ≤ d, et [min(a, c), max(b, d)] couvre les deux. Chaque fusion supprime un intervalle, donc le processus s’arrête, et lorsqu’un parcours complet ne trouve aucun chevauchement, aucun des intervalles restants ne partage de point avec un autre. Un seul parcours ne suffit pas : un intervalle fusionné est plus large et peut désormais atteindre un intervalle avec lequel sa partie plus petite avait été comparée plus tôt au cours du parcours.

Un parcours compare environ n²/2 paires et il peut falloir jusqu’à n parcours : O(n³). Un seul parcours sur 10^4 intervalles représente déjà 5 × 10^7 comparaisons.

Algorithme

Copiez starts et ends, et conservez un décompte n des intervalles actifs.
Comparez chaque intervalle i à tous les intervalles suivants j. S’ils se chevauchent, étendez i pour couvrir j, déplacez le dernier intervalle actif dans l’emplacement j et diminuez n de un.
Après une fusion, vérifiez à nouveau l’emplacement j, car un autre intervalle s’y trouve maintenant.
Répétez les parcours jusqu’à ce que l’un d’eux n’effectue aucune fusion.
Associez chaque début actif à sa fin, triez les paires par début et renvoyez-les.

def mergeIntervals(starts, ends):
    s = list(starts)
    e = list(ends)
    n = len(s)
    changed = True
    while changed:
        changed = False
        i = 0
        while i < n:
            j = i + 1
            while j < n:
                if s[j] <= e[i] and s[i] <= e[j]:
                    # Intervals i and j overlap: interval i absorbs interval j.
                    s[i] = min(s[i], s[j])
                    e[i] = max(e[i], e[j])
                    # Move the last interval into slot j and drop the last slot.
                    n -= 1
                    s[j] = s[n]
                    e[j] = e[n]
                    changed = True
                else:
                    j += 1
            i += 1
    return sorted([s[k], e[k]] for k in range(n))

Trier par début et parcourir une seule fois

Intuition

Après le tri par début, l’intervalle suivant ne commence pas avant quoi que ce soit dans le dernier groupe, qui se termine à e. Si son début est inférieur ou égal à e, il chevauche le groupe ou le touche et le rejoint, et e devient la plus grande des deux extrémités. Si son début est après e, aucun intervalle ultérieur ne peut non plus revenir dans le groupe, car les intervalles suivants commencent plus à droite. Le groupe est terminé et l’intervalle en ouvre un nouveau.

Le tri coûte O(n log n) et le parcours examine chaque intervalle une seule fois. Les groupes se ferment de gauche à droite, donc le résultat est trié par début.

Algorithme

Associez chaque début à sa fin : l’intervalle i est [starts[i], ends[i]].
Triez les paires par début.
Parcourez les paires triées. Si le résultat est vide, ou si la paire commence après la fin du dernier intervalle fusionné, ajoutez la paire comme nouvel intervalle.
Sinon, définissez la fin du dernier intervalle fusionné comme étant la plus grande valeur entre sa fin et la fin de la paire.
Renvoyez la liste fusionnée.

def mergeIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            if end > merged[-1][1]:
                merged[-1][1] = end
        else:
            merged.append([start, end])
    return merged

Pièges et cas limites

Comparer avec < au lieu de ≤. Les intervalles qui se touchent, tels que [1, 4] et [4, 5], doivent être fusionnés.
Définir la fin sur celle du nouvel intervalle au lieu de choisir la plus grande des deux. [1, 10] suivi de [2, 3] doit rester [1, 10].
Trier starts seul, puis lire ends aux nouvelles positions, de sorte qu'un début se retrouve associé à la fin d'un autre intervalle. Commence par les associer, ou trie les indices.
Comparer avec l'intervalle d'entrée précédent au lieu du dernier intervalle fusionné. Dans [1, 10], [2, 3], [4, 5], le troisième intervalle se trouve à l'intérieur de [1, 10], même s'il ne touche pas [2, 3].
En C, ne pas définir *returnSize au nombre d'intervalles fusionnés et la taille de chaque colonne à 2.

Questions fréquentes3

Quelle est la complexité temporelle de Merge Intervals ?

La solution par tri et balayage s’exécute en O(n log n) pour n intervalles : le tri coûte O(n log n) et le balayage O(n). Elle utilise O(n) d’espace supplémentaire pour les paires triées et le résultat.

Pourquoi trier les intervalles par début et non par fin ?

Trié par début, un intervalle ne peut chevaucher que le groupe que tu es en train de construire ; une seule comparaison avec la fin de ce groupe suffit donc à tout décider. Trié par fin, un intervalle ultérieur peut commencer avant des groupes que tu as déjà clôturés : [5, 6] vient avant [1, 10], et un balayage vers l’avant conserverait à tort 5 comme début.

Peux-tu fusionner les intervalles sans espace supplémentaire ?

Oui, si tu peux modifier l’entrée. Trie les intervalles sur place, puis écris chaque intervalle fusionné au début du même tableau et conserve l’indice du dernier intervalle écrit. La complexité temporelle reste O(n log n), et le seul espace supplémentaire utilisé est celui nécessaire au tri dans ton langage.

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

Test #1

Test #2

Arguments

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

Résultat attendu

[[1, 7], [12, 14]]