Discussion :

[Pothot]

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

[PRomu@ld]

Autrement dit, c'est quoi maximum d'évènements qui ont eu lieu en même temps...

Je n'ai rien compris

[Graffito]

Je n'ai rien compris

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 ???

[Pothot]

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 ???

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...

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.

[pseudocode]

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

[Pothot]

Tu peut le faire en 2 passes:

1er passe: algo 'sweep'

Désolé pour mon ignorance mais, ca ressemble à quoi un algo sweep . Et comment je peux l'appliquer pour mon problème.

[pseudocode]

Désolé pour mon ignorance mais, ca ressemble à quoi un algo sweep . Et comment je peux l'appliquer pour mon problème.

y'a pas de mal...

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

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)

2. on parcours la liste et on incremente/decremente le compteur suivant le type de date: (s) => +1 et (e) => -1

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

3. On releve la position du compteur max:

valeur max = 4
position = 12:16 (s)

4. On cherche les 4 rendez-vous qui se déroulent a 12:16

2- 12:01 à 12:20
4- 12:10 à 12:59
6- 12:15 à 12:25
7- 12:16 à 12:20

[TgRoX]

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