• [^] # Re: Problème 2

    Posté par . En réponse au message Challenge Codingame n°3. Évalué à 3. Dernière modification le 30 janvier 2013 à 12:46.

    Tu considères les jobs par date décroissante (en partant de la dernière jusqu'à la première). Pour chaque job, tu vérifies si tu peux le lancer en fonction des jobs (postérieurs) déjà lancés. Mon code pas très propre :

     struct job
 {
 int j,d;
 };
 static int compare (void const *a, void const *b)
 {
 struct job const *pa = a;
 struct job const *pb = b;
 return pb->j - pa->j;
 }
 int main()
 {
 int n;
 scanf("%d", &n);
 struct job jobs[100000];
 for (int i = 0; i < n; i++)
 scanf("%d %d",&jobs[i].j,&jobs[i].d);
 qsort (jobs, n, sizeof *jobs, compare);
 int x=2000000, total=0;
 for (int i = 0; i < n; i++) {
 if (jobs[i].j+jobs[i].d<=x){
 ++total;
 x=jobs[i].j;
 }
 }
 printf("%d",total);
 return 0;
 }

    Ça marche bien, sauf que dans la vraie vie on sait rarement à l'avance quels seront les futurs jobs.