Problème concernant des intervalles
Bonjour à tous,
Je suis actuellement en train de chercher la solution à un exercice qui me pose pas mal de soucis. Je l'explique :
En entrée, une liste d'intervalles représentant le temps de travail d'une personne (en secondes) est donnée. Le but est de donner en sortie le temps de présence maximum de cette personne. Voici un exemple :
Le premier chiffre représente le nombre d'intervalles.
6
1 3
7 15
20 22
2 5
9 11
12 18
La personne est présente de la seconde 1 à la seconde 5, puis de la seconde 7 à la seconde 18, et finalement de la seconde 20 à la seconde 22, soit un total de 4 + 11 + 2 = 17 secondes.
les conseils donnés pour l'exercice sont les suivants :
Trier les segments par position de début croissante.
Maintenir deux valeurs : d'une part le total en cours, et d'autre part la fin de segment la plus à droite déjà vue.
J'ai créé une structure que j'ai ensuite triée par ordre croissant de début d'intervalles. Plusieurs solutions sont possibles mais j'ai du mal à les implémenter (les comprendre ?). Je précise que j'apprends l'algo en faisant du C++.
La première :
Lorsque je dessine les intervalles sur une feuille, je représente celles-ci sous forme d'escalier. Chaque intervalle sur une ligne différente. Je me dis que ça serait bien qu'il n'y ai plus qu'une seule ligne à la fin, donc, que je fusionne les intervalles qui font partie d'autres intervalles. Ensuite je parcourrais cette ligne, et dès que je vois un trou dans la ligne, cela signifie qu'il n'y a personne au poste, j'effectue ma soustraction puis je continue le traitement.
La seconde :
C'est une solution que j'ai trouvée en fouillant un peu sur le forum. J'ai demandé quelques précisions sur ce post mais vu son âge, il n'est pas impossible que personne ne l'ai vu. Il s'agit de ce post :
http://www.developpez.net/forums/d43...AAKgAAAJSUAgA=
je vais faire un copié/collé de la réponse fournie au posteur :
"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."
J'ai représenté cette solution sur papier, ce qui donnerait (ligne du haut = intervalles ; ligne du bas = compteur
Intervalles : 1 2 3 5 7 9 11 12 15 18 20 22
Compteur: 1 2 1 0 1 2 1 2 1 0 1 0
En suivant cette logique, dès que le compteur tombe à zéro, cela veut dire que l'on n'est dans aucune intervalle. J'aime bien cette solution, mais je me demande alors comment identifier les chiffres, de manière à ce que l'on sache s'il s'agit d'un début d'intervalle ou d'une fin. Ici aussi, j'avais pensé à faire une structure avec le chiffre en entier et la dénomination(e ou s) en caractère, mais je n'arrive pas à implémenter l'opérateur de tri pour utiliser la fonction sort() (je rappelle que je code en c++, même s'il s'agit d'un entrainement algorithmique).
Donc voilà, il y a des idées, mais j'ai du mal à les implémenter. Un peu d'aide serait la bienvenue !
Merci :)
