Bonjour;

Je suis actuellement bloqué sur un exercice de chez ioi France, mon code passe 18 tests sur 21. Les derniers tests échouent pour dépassement de la limite du temps.

Voici l'ennocée:
Un festival de musique met chaque jour un groupe en scène, un groupe pouvant jouer plusieurs jours différents. En tout, nbGroupes groupes vont jouer pour ce festival et ce dernier durera nbJours jours.

Vous connaissez l'ordre dans lequel les différents groupes vont se succéder au cours du festival à raison d'un par jour, et vous désirez assister au concert de chacun de ces groupes au moins une fois. Vous écrivez donc un programme capable de determiner la longueur de la plus petite séquence contiguë de jours permettant de voir au moins une fois chaque groupe.
Limites de temps et de mémoire (C)

Temps : 1 s sur une machine à 1 GHz.
Mémoire : 32 000 ko.

Contraintes

1 <= nbJours <= 100 000, où nbJours est le nombre de jours du festival.
1 <= nGroupes <= nbJours, le nombre de groupes jouant pour le festival.

Entrée

La première ligne de l'entrée contient deux entiers : nbJours et nbGroupes.

La ligne suivante contient nbJours entiers, le ie entier correspondant à l'identifiant 1 <= groupei <= nbGroupes du groupe jouant le ie jour.
Sortie

Votre programme doit afficher un unique entier : le plus petit nombre de jours consécutifs nécessaires pour voir au moins une fois chaque groupe jouer.
Exemple

entrée :

12 5
1 3 2 2 5 4 3 2 5 5 1 4

sortie :

6

Voici mon code:

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <stdlib.h>
int nbJours, nbGroupes;
int *planning = NULL, *dejaVu = NULL;
int minDays(int minimum);
int main()
{
   int i;
   scanf("%d%d", &nbJours, &nbGroupes);
 
   planning = malloc(sizeof(int) * nbJours);
   dejaVu = malloc(sizeof(int) * nbJours);
   for(i = 0; i < nbJours; i++)
   {
      scanf("%d", &planning[i]);
      dejaVu[i] = 0;
   }
 
   printf("%d", minDays(nbJours));
 
   free(dejaVu);
   free(planning);
}
int minDays(int minimum)
{
   int debut = 0, iFin = 0, compteur = 0;
   int iGroup = 0;
   while(iFin < nbJours)
   {
      if(dejaVu[planning[iFin]] == iGroup)
      {
         dejaVu[planning[iFin]] = iGroup+1;
         compteur++;
      }
 
      while(compteur == nbGroupes)
      {
         if((iFin+1 - debut) < minimum)
            minimum = (iFin+1 - debut);
         iGroup++;
         debut++;
         compteur = 0;
         iFin = debut-1;
      }
      iFin++;
   }
   return minimum;
}
J'utilise un tableau dejaVu pour valider un groupe complet de jours. Je parcours le tableau planning plusieurs fois. Je pense que c'est cela qui plombe la vitesse.
Merci d'avance pour l'aide apportée !