J'ai suivi de l'ADT (non trié): Ils représentant par exemple cette situation:
Comment faire la phase de fusion (flèche verte dans l'exemple)? De toute évidence, j'ai besoin de itérer sur la liste et chaque segment se compare à tous les autres segments, et pour chaque couple si possible de faire une fusion simple (c'est facile). Mais ensuite dans la deuxième itération, j'ai besoin de retourner au début de la liste et de recommencer, etc ... donc j'ai du mal à trouver comment cet algorithme convergera. EDIT: Les segments peuvent être circulaires - de 1,75pi à 0.5PI, etc. Liste 
4 Réponses :
Trier vos segments par point de départ.
Puis, pour chaque segment, si son point de départ se situe entre le point de départ et l'extrémité du segment précédent et que son point d'extrémité est supérieur au point d'extrémité du segment précédent, définissez le point d'extrémité du segment précédent sur ce point d'extrémité de ce segment et retirez-le. / ignorer le segment actuel.
Si le segment actuel est complètement inclus dans le segment précédent, alors retirez-le / ignorez-le.
Ceci est Faites attention à la façon dont vous faites la suppression ou l'ignorance. Il devrait s'agir d'une opération O (n journal n) en raison du tri et que vous n'avez pas besoin de comparer chaque segment avec tous les autres segments.
O (1) . Par exemple, conservez une variable qui stocke toujours le segment précédent non supprimé et peut-être un drapeau pour les segments supprimés afin que vous sachiez ceux qui collectent à la fin. .ReMove () Opérations sur les collections peut être o (n) , et vous voulez éviter cela.
@Iviad merci de l'analyse de la complexité
Trier les segments par temps de départ.
Créer une pile qui stockera les intervalles fusionnés.
Ajoutez le premier élément du tableau trié à la pile, puis pour chaque élément du tableau, puis pour chaque élément de la matrice, Comparez-le à l'élément en haut de la pile
si l'heure de début est supérieure à la durée de fin de l'élément en haut de la pile, ajoutez l'intervalle à la pile. < P> Si l'heure de début est inférieure à la durée de fin de l'élément en haut de la pile, mettez à jour l'heure de fin de l'élément en haut de la pile pour correspondre à l'heure de fin du nouvel élément. < P> Lorsque l'ensemble de la matrice est traité, la pile résultante doit contenir les intervalles fusionnés.
implémentation sur java:
Mettez tous les points d'extrémité dans un seul tableau et attribuez-leur une polarité ( Lorsque vous allez passer à parcourir la liste en augmentant la valeur, il suffit de mettre à jour un compteur de segments de chevauchement. puis, trié, donne les comptes (initialisés à d'où les limites d'intervalle (sur les transitions < code> 0 à> 0 ou Ceci peut également être fait purement Vous triez le puis traverser la liste comme une fusion de deux listes triées (à l'aide de deux index indépendants) et maintenez le compteur de chevauchement. Vous pouvez écraser les limites en place, car le résultat de la fusion n'a pas plus d'intervalles. à partir de Les deux listes sont accidentellement déjà trié. passez à la fusion, qui sélectionnera les éléments dans l'ordre et le résultat final est obtenu en changeant des valeurs en cas de cravates sur les limites, il est préférable de traiter le + puis - ). Puis triez la liste. 0 ) > 0 à 0 )
Démarrer et les valeurs extrémité séparément, en place (ne déplacez pas le segments dans son ensemble); De cette façon, les polarités restent implicites.
+ et le et le - dans une commande de telle sorte que vous évitez d'émettre deux limites égales.
Je vais ajouter à d'autres réponses l'approche de la circularité, c'est-à-dire que devriez-vous faire si vous avez des segments en boucle sur 2pi.
Il y a deux façons de gérer cela. L'un est trop divisé chaque segment de ce type en deux: un qui va de partout au 2Pi, l'autre va de zéro à l'autre. Après cela, résolvez le problème comme s'il n'est pas circulaire, puis si vous avez un segment à partir de zéro et un segment se terminant à 2pi, puis je viens de les fusionner.
Une deuxième approche concerne spécifiquement la réponse de Yves Daoust. Il vous suffit de savoir combien de segments couvrent le point zéro (vous pouvez facilement calculer cela); Après cela, vous initialisez les "comptes" non à zéro, mais avec ce nombre de segments de couverture.
Votre liste est-elle commandée ou aléatoire?
Est-ce la circulaire? C'est-à-dire que vous pouvez avoir un segment à partir de 1h500, puis sur 2PI à 0.5PI?
@Petr je n'ai pas fait attention à cela, mais en fait oui - il peut être circulaire ...