Génération de sous-matrices de plages chevauchantes

Je m'appelle Timothy Sassone. Je travaille sur le développement d'un logiciel de programmation en C#, mais j'ai eu des problèmes. Cette dernière partie du programme est destinée à prendre une grande liste d'événements hebdomadaires (stockés en tant que jour (s) de la semaine et heure de début et de fin) et à les trier en sous-listes contenant des événements qui se chevauchent (tel que personne n'aurait pu assister à deux des événements de la sous-liste).Génération de sous-matrices de plages chevauchantes

Pour l'instant, il le fait en trouvant l'événement "le plus long" de la liste ((endTime-startTime) * numDays), et en l'ajoutant à chaque sous-liste. Il trouve ensuite tous les «conflits» (événements qui ne se chevauchent pas) et les résout en supprimant le moins de cours possibles. J'ai beaucoup, mais avec le nombre de plages que j'ai à traiter, je me retrouve avec un nombre plutôt élevé de sous-listes. Y a-t-il une meilleure façon de diviser la liste, de sorte que je me retrouve avec moins de sous-listes? J'ai considéré une méthode de force brute, essayant simplement toutes les possibilités et allant avec le meilleur, mais le nombre de gammes est assez élevé (entre 100 et 500 en moyenne), ce qui pourrait être plutôt lent. Toute suggestion ou pointeur serait très apprécié.

Merci pour votre temps,

Timothy Sassone

Source

2011-03-04 Timothy S.

Je ne pense pas que je l'obtiens. Si event1 se chevauche avec event2 et event2 se chevauche avec event3, devraient-ils tous aller dans la même sous-liste même si event1 pourrait ne pas chevaucher event3? – Jan

Non. L'objectif est que les listes soient formées de manière à ce que personne ne puisse assister à deux des événements d'une liste donnée. Si event1 se chevauchait avec event2 et event3, mais event2 et event3 ne se chevauchaient pas, ils pouvaient participer à event2 et event3. Je programmerai d'autres événements basés sur ces listes, et le temps pour les nouveaux événements ne pourra que se chevaucher (empêchant ainsi quiconque d'assister aux deux) si les deux événements hebdomadaires impliqués se chevauchent également. Merci pour votre temps! –

La bibliothèque Période pour .NET http://www.codeproject.com/KB/datetime/TimePeriod.aspx inclut le TimePeriodIntersector pour rechercher périodes qui se chevauchent.

Les chevauchements sont calculés avec un algorithme linéaire et rapide par comptage/tri tous les instants sur la ligne de temps.

Et l'utilisation de TimePeriodIntersector ressemble:

// ---------------------------------------------------------------------- 
public void TimePeriodCombinerSample() 
{ 
    TimePeriodCollection periods = new TimePeriodCollection(); 

    periods.Add(new TimeRange(new DateTime(2011, 3, 01), new DateTime(2011, 3, 10))); 
    periods.Add(new TimeRange(new DateTime(2011, 3, 04), new DateTime(2011, 3, 08))); 

    periods.Add(new TimeRange(new DateTime(2011, 3, 15), new DateTime(2011, 3, 18))); 
    periods.Add(new TimeRange(new DateTime(2011, 3, 18), new DateTime(2011, 3, 22))); 
    periods.Add(new TimeRange(new DateTime(2011, 3, 20), new DateTime(2011, 3, 24))); 

    periods.Add(new TimeRange(new DateTime(2011, 3, 26), new DateTime(2011, 3, 30))); 

    TimePeriodCombiner<TimeRange> periodCombiner = new TimePeriodCombiner<TimeRange>(); 
    ITimePeriodCollection combinedPeriods = periodCombiner.CombinePeriods(periods); 

    foreach (ITimePeriod combinedPeriod in combinedPeriods) 
    { 
    Console.WriteLine("Combined Period: " + combinedPeriod); 
    } 
    // > Combined Period: 01.03.2011 - 10.03.2011 | 9.00:00 
    // > Combined Period: 15.03.2011 - 24.03.2011 | 9.00:00 
    // > Combined Period: 26.03.2011 - 30.03.2011 | 4.00:00 
} // TimePeriodCombinerSample

Source

2011-04-02 20:33:28 Jani

Génération de sous-matrices de plages chevauchantes

Répondre

Questions connexes