Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Intervalle contenant le plus d'autres intervalles
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
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.
Consignes aux jeunes padawans : une image vaut 1000 mots !
- Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
- Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
-ton poste tu dois marquer quand la bonne réponse tu as obtenu.
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 ?
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
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 ?
Lol c'est une expression...Envoyé par SEB1702
C'est juste une boucle ..
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
merci de votre aide .
le probleme est resolu.
Et comment ?
Tu peux nous donner une indication stp ?
"Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".
Consultant indépendant.
Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
C, Fortran, XWindow/Motif, Java
Je ne réponds pas aux MP techniques
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager