Algo fusion d'intervalles

Salut,

Voilà, j'ai des intervalles de temps représentés par 2 listes (liste temps début et une liste temps fin)

Par exemple j'ai un intervalle de temps qui démarre à 1 seconde et finit à 3secondes, je note ça 1 3.

Prenons différents intervalles
1 3
2 3
4 5
6 10
9 11
12 15
13 16

Je cherche un algo rapide et efficace, permettant de fusionner les intervalles qui peuvent l'être. Si on a un intervalle de 1 à 3 secondes et un autre de 2 à 3 secondes, je peux les unir. J'obtiens une liste minimale d'intervalles distincts

1 3
4 5
6 11
12 16

Merci de votre aide

Le mieux serait que tu commences par dire comment tu as commencé à l'envisager ? Il y a plusieurs façons de prendre le problème.

PS : si tu bloques vraiment, que tu n'arrives pas à démarrer, demande toi comment toi tu le ferais, à la main.

A mon avis, le plus simple est de créer les fusions petit à petit.

Tu prends le premier intervalle (ou au hasard).

Et ensuite, tu prends les intervalles les uns à la suite des autres, et tu identifies quels sont les intervalles (ceux qui ont déjà été traités) qui chevauchent celui en cours de traitement. Tu fusionnes alors tous ceux qui se chevauchent (en y incluant celui qui est en cours de traitement).

Commence par trier par ordre croissant du début de l'intervalle, ensuite le problème me semble trivial.

Ecrire d'abord une fonction 'intersect' qui est un prédicat prenant en argument deux intervalles [a,b] et [c,d] et décidant s'ils se coupent ou non.
Ecrire ensuite une fonction 'fusion' prenant en argument deux intervalles se coupant et retournant l'intevalle réunion.
Organiser ensuite les intervalles en collection (tableau, liste, etc..)
Comparer le premier à tous les autres et chaque fois qu'on trouve dans la liste des autres un intervalle qui 'intersect' le premier remplacer le premier par son union avec celui-ci et supprimer l'intervalle en question de la liste.
A la fin du traitement on a un premier intervalle plus grand que le premier initial, et une liste plus courte que la liste initiale et ne comportant que des intervalles ne coupant pas le premier, il suffit alors d'itérer sur cette nouvelle liste.

ou sinon, le désormais classique "sweep":

Données d'entrée

Code:

---

1 2 3 4 5 6 7 8

#1 = 1 3 #2 = 2 3 #3 = 4 5 #4 = 6 10 #5 = 9 11 #6 = 12 15 #7 = 13 16

---

Table de sweep

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

t Actif au temps t --------------------- 1 #1 2 #1,#2 3 #1,#2 4 #3 5 #3 6 #4 9 #4,#5 10 #4,#5 11 #5 12 #6 13 #6,#7 15 #6,#7 16 #7

---

Les fusions possibles sont les entrées qui ont au moins 2 élements actifs:

Fusion: (#1,#2)
Fusion: (#4,#5)
Fusion: (#6,#7)

Citation:

---

Envoyé par pseudocode

sinon, le désormais classique "sweep":

---

J'ai pas compris, c'est quoi le sweep ?

Attention, il y a des cas particuliers que j'ai découverts en faisant la même chose (avec des adresses IP au lieu de nombre mais c'est pareil)

[5-10] peut fusionner avec [11-21]
[1-4] peut fusionner avec [5-21]
[1-21] peut fusionner avec [10-12]

Citation:

---

Envoyé par Zavonen

A la fin du traitement on a un premier intervalle plus grand que le premier initial, et une liste plus courte que la liste initiale et ne comportant que des intervalles ne coupant pas le premier, il suffit alors d'itérer sur cette nouvelle liste.

---

Pas tout à fait vrai

A la fin du traitement on a un premier intervalle plus grand que le premier initial
==> oui
une liste plus courte que la liste initiale
==> oui
ne comportant que des intervalles ne coupant pas le premier
==> pas toujours

ainsi:
[1-10] [15-21] [10-16]
A la fin de la 1ere itération on a:
[1-16] [15-21]
et il faut recommencer avec le 1er element pour tester avec les intervalles restant

Je pense qu'il faut en plus que la collection initiale soit triée pour que ce que tu dis devienne vrai

Citation:

---

A la fin du traitement on a un premier intervalle plus grand que le premier initial
==> oui
une liste plus courte que la liste initiale
==> oui
ne comportant que des intervalles ne coupant pas le premier
==> pas toujours

---

Ta remarque est parfaitement vraie, mais cette dernière condition est inutile, elle est même stupide (autant pour moi), car elle signifie que l'algo s'arrête après la première itération.

Citation:

---

Envoyé par Zavonen

Ecrire d'abord une fonction 'intersect' qui est un prédicat prenant en argument deux intervalles [a,b] et [c,d] et décidant s'ils se coupent ou non.
Ecrire ensuite une fonction 'fusion' prenant en argument deux intervalles se coupant et retournant l'intevalle réunion.
Organiser ensuite les intervalles en collection (tableau, liste, etc..)
Comparer le premier à tous les autres et chaque fois qu'on trouve dans la liste des autres un intervalle qui 'intersect' le premier remplacer le premier par son union avec celui-ci et supprimer l'intervalle en question de la liste.
A la fin du traitement on a un premier intervalle plus grand que le premier initial, et une liste plus courte que la liste initiale et ne comportant que des intervalles ne coupant pas le premier, il suffit alors d'itérer sur cette nouvelle liste.

---

Cet algorithme est en O(n^2), on peut faire du O(n log n) ou même du O(n) (si la liste est déjà triée (ce qui est préférable pour l'exploiter de tout façon), ou si on peut employer un tri en O(n)). On peut ensuite fusionner tant qu'on peut à un point de la liste puis passer au suivant si il n'y a plus de fusion possible. Par exemple en Haskell, on pourrait faire ça avec :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

type Interval = (Int,Int)   -- | This function takes a sorted (by lower born) -- | list of intervals and return a sorted list of -- | intervals fused so that none overlaps fuse :: [Interval] -> [Interval] fuse = foldr merge [] where merge i [] = [i] merge i@(b,e) iis@((b',e'):is) = if b' < e+1 then (b,max e e'):is else i:iis

---

--
Jedaï

Citation:

---

Cet algorithme est en O(n^2),

---

Cet algorithme est en O(n^2), au pire !
Car ce calcul néglige la disparition des intervalles fusionnés à chaque étape.

Citation:

---

Envoyé par Zavonen

Cet algorithme est en O(n^2), au pire !
Car ce calcul néglige la disparition des intervalles fusionnés à chaque étape.

---

L'algorithme est en Omega(n) et en O(n^2), je ne vois pas ce que rajouter "au pire" vient faire la-dedans. Il existe évidemment des cas où l'algorithme est bien en Théta(n^2) ne serait-ce que le cas où il n'y a pas de fusion (qui n'est peut-être pas si rare que ça, selon le domaine).

De toute façon, l'algorithme que j'ai proposé est évidemment un raffinement de ton idée (et avait déjà été plus ou moins suggéré par plusieurs personnes dans le thread) qui ne peut qu'améliorer les choses.

--
Jedaï