Discussion :

[duguek]

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

[Alp]

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.

[PRomu@ld]

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

[Jean-Marc.Bourguet]

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

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

[pseudocode]

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

Données d'entrée

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[Jedai]

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 Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

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ï