Discussion :

[SEB1702]

bonjour,
je coince sur un pb que m'a pose mon neuveu

on se donne un ensemble de N intervalles.
on recherche dans cet ensemble celui qui contient le plus des autres intervalles.
il faut faire nettement mieux que N*N ,que la maniere naive donc...

mais voila je coince..
merci de votre aide

[ToTo13]

On m'a posé un jour ce genre de problème : pour un intervalle donné, trouver tous les intervalles qui sont à l'intérieur ou qui l'intersecté.
De mémoire la solution était dans la structure de représentation : un arbre.
- le noeud racine contient un intervalle.
- les noeuds à gauche sont les intervalles de valeurs (extrémités) plus petites qui ne l'intersecte pas.
- les noeuds à droite sont les intervalles de valeurs plus grandes qui ne l'intersecte pas.
- les centraux sont les intervalles contenus.
- les intervalles qui intersectent sont dans une liste reliée au noeud.
Cette structure devrait (à tester pour voir si ça s'applique aussi bien) améliorer ton problème.

[souviron34]

Une solution :

• trier les intervalles par leur début (O(N log(N))
• passer à travers la liste et simplement compter les débuts d'autres jusqu'à arriver à la fin de l'intervalle considéré O(N log(N)) sans doute, non ? (équivalent Bentley-Ottman pour intersections de segments)

ou bien

• trier par taille décroissante et début croissant
• passer à travers

Non ?

[SEB1702]

merci je vais reflechir a vos indications ...

mais pouvez vous m'expliquer ou me dire ou trouver des renseignements sur la notion de passer a travers ?

[souviron34]

mais pouvez vous m'expliquer ou me dire ou trouver des renseignements sur la notion de passer a travers ?

Lol c'est une expression...

C'est juste une boucle ..

[SEB1702]

merci de votre aide .
le probleme est resolu.