Discussion :

[benji07]

Bonjour,
je suis a la recherche d'un algorithme pour verifier si une plage horaire est valide.

je m'explique, j'ai pour un jour donnée une liste de plage horaire (heure de début + heure de fin)

et il ne faut pas que les plages horaire ce chevauche.

ex:
10:00-12:00 & 14:00-16:00 = valide
10:00-12:00 & 11:30-16:00 = erreur

le truc c'est que le nombre de plage horaire peut varier, sinon ça aurait été trop simple.

je cherche un algo tout fait si ça existe déja, sinon je chercherai

[pseudocode]

Bah... tu peux trier tes plages horaires par heure de début, et vérifier que chaque plage se termine avant le début de celle d'après.

[Zavonen]

Convertis tous tes temps en secondes, et tu es ramené à un simple problème de chevauchement d'intervalles.

[benji07]

euh, tu aurais pas un example ? car la comme ça je bloque un peu

maintenant j'ai un tableau avec n ligne, chacune a 2 colonnes ('start' et 'end' qui sont les temps en secondes)

[souviron34]

réfléchis et prend un papier et un crayon

Sachant que dans ton tableau, par exemple comme ceci

Code :

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

1
2
3
4
start      end
12350    14600
13800    17000
14700    21000

[benji07]

Pour le moment j'ai ça, mais y n'y as pas moyen de faire descendre la complexité en dessous de n²

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
$h_time = array_reverse($h_time);
$index_error = array();
$nb = count($h_time);
for($i = 0; $i < $nb; $i++){
  for($j = 0; $j < $nb; $j++){
    if($i == $j) continue;
    // si le début ou la fin est compris entre les 2
    if(($h_time[$i]['start'] > $h_time[$j]['start'] && $h_time[$i]['start'] < $h_time[$j]['end'])
      ||($h_time[$i]['end'] > $h_time[$j]['start'] && $h_time[$i]['end'] < $h_time[$j]['end'])){
         $index_error[] = $nb - $i;
       }
     }
   }

[Zavonen]

Commence par les classer par ordre de début avec un quick-sort en nlog(n).
Après tu regardes si le début du second est avant la fin du premier, et ainsi de suite, tu arrives à nlog(n)+n qui est un peu mieux que n².

[Alp]

Commence par les classer par ordre de début avec un quick-sort en nlog(n).
Après tu regardes si le début du second est avant la fin du premier, et ainsi de suite, tu arrives à nlog(n)+n qui est un peu mieux que n².

nlog(n)+n dans le pire des cas !
Si dès le début tu en trouves qui se chevauchent, tu t'arrêtes et tu réponds que ce n'est pas valide.
Du coup, en moyenne nlog(n)+n/2

Je ne pense pas qu'il soit possible de faire beaucoup mieux. J'ai une idée un peu tordue mais pas sûr que ça marche. Je vais y réfléchir.

[benji07]

ouais, mais le truc c que je doit renvoyer l'indice des elements qui ce chevauche, et puis finalement les perf ne sont plus importante, dans je vais laisser le code que j'ai mis

[Alp]

D'accord. Mais à quoi te servent les indices ?

[benji07]

pour le rendu