Bonjour à tous,

Je sais que ce salon n'est peut-être pas le plus adapté pour ce type de question mais je n'ai pas trouvé ailleurs .

Voilà mon problème, j'ai besoin d'un algorithme performant car j'en ai trouvé quelques uns mais l'ordre de calcul minimum que j'ai trouvé au minimum est de O[(2^n)-1]. Bref c'est plutôt couteux sachant que j'ai 11 000 données à étudier.

Je vous explique la situation, j'ai un type de donnée de la sorte:

element:

nom1: valmin , valmax
nom2: valmin, valmax
....
nomN: valmin, valmax

Mon algorithme prend en entrée un ensemble d'élement ayant un ensemble de valeur avec valMin = valMax.

Par exemple:

e1:
a 1 1
b 2 2
c 2 2

e2:
a 2 2
b 4 4
c 5 5

e2:
a 3 3
b 3 3
c 6 6

Le but de mon algorithme est de définir les intervalles reliant ces types, dans cet exemple, le résultat obtenu serait:

e1:
a 1 1
b 2 2
c 2 2

e2:
a 2 2
b 4 4
c 5 5

e2:
a 3 3
b 3 3
c 6 6

t1:
a 1 3
b 2 4

t2 :
b 3 4
c 5 6



La jointure entre un element A et un element B se fait de cette facon:

admettons que nous ayons:

a1:
a 2 2
b 3 3
c 6 6

et

a2:
a 3 3
b 10 10
c 5 5

alors la jointure entre ces deux éléments sera:

t :
a 2 3
c 5 6
(pas de b car il n'y a pas de lien entre 3 et 10)

ça c'est simple à obtenir.

Le but de l'algorithme est de calculer un ensemble d'intervalles sans "trou".


Admettons que nous ayons :

e1:
a 1 1
b 2 2
c 2 2

e2:
a 3 3
b 3 3
c 6 6

Nous ne pouvons obtenir que

b 2 3

en revanche pour obtenir

a 1 3
b 2 3
c 2 6

il faut qu'il y ai au préalable (dans une liste temporaire, c'est comme ça que j'ai fait)

a 2 2 ou a 1 2 ou a 2 3 ou a 13
b 2 2 ou b 3 3 ou b 2 3
c 2 5 ou c 3 6 ou c 2 5 ou c 26

Bref c'est un peu compliqué, je ne sais pas si j'ai bien exprimé mon problème mais j'ai besoin d'aide car je n'arrive pas à avoir quelque chose de performant...

Merci beaucoup!