Discussion :

[azzhunter]

Bonjour,

j'ai une liste de taches.
Une tache est constituée de : un identifiant, une date de depart, et une durée.

Je voudrais savoir si dans ma liste de taches, est ce que à un moment il y a X taches qui se chevauche.

Soit ci dessous ma liste de taches ( "-" est l'unité de durée)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
t->
 
<ol class="decimal"><li style="">---</li><li style="">--</li><li style="">-</li><li style=""> ---</li><li style=""> --</li><li style="">  ---</li><li style="">  -</li><li style="">   --</li><li style="">   -</li></ol>

Ici, je voudrais avoir la liste de tache pour 5 chevauchements,
soit les taches 1 4 5 6 7.

la premiere solution que j'ai trouvé etait :

pour chaque tache (noté ref), on liste toutes les taches pour lesquelles la date de debut est entre ref.datedebut et ref.datefin (obtenu par ref.datedebut+ref.duree)

hors cela ne fonctionne pas puisqu'on peut avoir plusieurs "domaines" d'intersection
par exemple, avec ce raisonnement pour la tache 1, on aurait 7 taches qui se chevauchent (de 1 à 7), hors dans ce cas précis, les taches 3 et 4 ne se chevauchent pas alors qu'elle font parti du meme "domaine"


j'ai trituré le probleme dans pas mal de sens, mais je trouve toujours un cas qui fausse mon raisonnement.

Si quelqu'un a une idée, et qu'il veut bien la soumettre,
je le remerie d'avance

Cordialement,

Azzhunter

[Nemerle]

Ici, je voudrais avoir la liste de tache pour 5 chevauchements,
...
par exemple, avec ce raisonnement pour la tache 1, on aurait 7 taches qui se chevauchent

Précise, ce que tu veux n'est pas clair... d'où vient ce besoin de 5 chevauchements, c'est un exemple?

[azzhunter]

oui je desir obtenir la liste des X (ou plus) taches qui se chevauchent.

J'ai donné ici 5 comme exemple

[FrancisSourd]

L'idée est de faire varier t de 0 à la date de fin de la dernière tâche en fonction des débuts et fins de tâches.

Tu fais un tas A contenant les tâches à exécuter triées selon leur date de début. Il contient toutes les tâches au début.

Tu fais un tas B contenant les tâches en cours triées selon leur date de fin. Il est vide au début.

A chaque étape, tu regardes si le prochain événement sera un tâche qui commence ou une tâche qui finit (en regardant dans les deux tas triés). Si c'est une tâche qui commence, tu l'enlève de A et tu la mets dans B, sinon tu enlèves la tâche de B.

Le nombre de tâche dans B te donnes à chaque instant le nombre de tâches en cours. Si cela dépasse X, tu arêtes.

L'algo est en O(n log n)

[Zavonen]

On suppose que l'échelle des temps est ramenée à un axe réel.
On définit, les réels D1, F1 début et fin de la tâche 1
D2,F2 début et fin de la tâche 2
......
Dn, Fn début et fin de la tâche n
On ordonne l'ensemble fini de tous ces points mélangés.
D = Min de cet ensemble
F= max de cet ensemble
on considère maintenant la fonction suivante pour x dans l'intervalle [D,F]
N(x) = Nombre de tâches en exécution à l'instant x
La fonction N est constante par morceaux, elle ne peut présenter un saut que sur un Di où un Fi, il suffit donc de la déterminer sur un seul point de chaque intervalle déterminé par l'ensemble ordonné précédent (par exemple le milieu m).
Pour déterminer N(m) il suffit de compter les k tels que m >=Dk et m<= Fk, fastidieux mais simple.
Le plus gros du travail consiste donc à ordonner un ensemble de 2n points

[azzhunter]

Merci à vous,

j'ai opté pour l'algo de FrancisSourd,

ça marche tres bien, et les performances sont au dela de mes espérances,

En vous remerciant,

AzzHunter