Version imprimable
Bonjour à tous,
J'ai 2 séries (DateTime_Start) (DateTime_End). Je dois trouvé le nombre maximum chevauchements simultanés. Autrement dit, c'est quoi maximum d'évènements qui ont eu lieu en même temps... Quelqu'un a une idée comment s'y prendre?
Merci
Je n'ai rien compris :aie:Citation:
Autrement dit, c'est quoi maximum d'évènements qui ont eu lieu en même temps...
Je suppose que l'on doit composer les intervalles en "piochant" la date de début dans la série 1 et la date de fin dans la série 2 ???Citation:
Je n'ai rien compris
Effectivement les intervalles sont composés des date de début dans la série 1 et de date de fin dans la série 2 (trié par date de début)... Ce que je dois trouver, c'est le maximum d'évènements qui ont eu lieu simultanément...Citation:
Envoyé par Graffito
Ex:
1- 12:00 à 12:02
2- 12:01 à 12:20
3- 12:05 à 12:07
4- 12:10 à 12:59
5- 12:12 à 12:13
6- 12:15 à 12:25
7- 12:16 à 12:20
8- 12:21 à 12:30
Dans ce cas la réponse est 4. Les évènements 2,4,6,7.
Tu peut le faire en 2 passes:
1er passe: algo 'sweep' pour trouver le max de chevauchement (4) et l'heure au moment du max (12:16)
2nde passe: trouver les evenements qui ont lieu a l'heure du max
Désolé pour mon ignorance mais, ca ressemble à quoi un algo sweep :oops: . Et comment je peux l'appliquer pour mon problème.Citation:
Envoyé par pseudocode
y'a pas de mal... ;)Citation:
Envoyé par Pothot
Le sweep consiste a mettre a jour un compteur en parcourant dans l'ordre chronologique toutes des dates. A chaque fois que tu tombes sur une date de "start" tu augmentes ton compteur de 1, et a chaque fois que tu tombes sur une date de "end" tu le décrementes de 1.
Exemple pour ton cas:
1. On met toutes les dates dans une seule liste et on la trie par ordre chronologique
2. on parcours la liste et on incremente/decremente le compteur suivant le type de date: (s) => +1 et (e) => -1Citation:
12:00 (s)
12:01 (s)
12:02 (e)
12:05 (s)
12:07 (e)
12:10 (s)
12:12 (s)
12:13 (e)
12:15 (s)
12:16 (s)
12:20 (e)
12:20 (e)
12:21 (s)
12:25 (e)
12:30 (e)
12:59 (e)
3. On releve la position du compteur max:Citation:
INIT ---> 0
12:00 (s) 1
12:01 (s) 2
12:02 (e) 1
12:05 (s) 2
12:07 (e) 1
12:10 (s) 2
12:12 (s) 3
12:13 (e) 2
12:15 (s) 3
12:16 (s) 4
12:20 (e) 3
12:20 (e) 2
12:21 (s) 3
12:25 (e) 2
12:30 (e) 1
12:59 (e) 0
4. On cherche les 4 rendez-vous qui se déroulent a 12:16Citation:
valeur max = 4
position = 12:16 (s)
Citation:
2- 12:01 à 12:20
4- 12:10 à 12:59
6- 12:15 à 12:25
7- 12:16 à 12:20
Bonjour,
Je suis actuellement sur un problème du même type. Ce que je ne comprends pas dans ton explication sur l'algorithme de sweep, c'est comment, après avoir trié toutes les données dans une seule liste, tu détermines si c'est un "start" ou un "end". Dans mon exercice, j'ai ces données non triées :
1 3
7 15
20 22
2 5
9 11
12 18
Si je fais comme dans ton explication, je me retrouve avec un tableau ayant cette forme là :
1 2 3 5 7 9 11 12 15 18 20 22
Comment déterminer alors qui est un début et qui est une fin ? Je n'ai pas tout saisi :-/
Merci :)