icatalin

activitati student deadline greedy

Apr 22nd, 2018
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct interval
  5. {
  6.     int id, time, deadline;
  7. };
  8.  
  9. void citire(FILE *fin,int *n, struct interval *ptr)
  10. {
  11.     fscanf(fin,"%d",&(*n));
  12.     int i;
  13.  
  14.     for (i=0; i<*n; i++)
  15.     {
  16.         fscanf(fin,"%d %d",&ptr->time,&ptr->deadline);
  17.         ptr->id = i + 1;
  18.         ptr++;
  19.     }
  20.  
  21. }
  22.  
  23. void afisare(FILE *fout, int n, struct interval *ptr)
  24. {
  25.     fprintf(fout,"Vector sortat crescator dupa deadline:\n");
  26.  
  27.     int i;
  28.  
  29.     fprintf(fout,"%d\n",n);
  30.  
  31.     for (i=0; i<n; i++)
  32.     {
  33.         fprintf(fout,"id %d: %d %d \n", ptr->id, ptr->time, ptr->deadline);
  34.         ptr++;
  35.     }
  36.  
  37. }
  38.  
  39. void sortare(int n, struct interval *v) //sortare cu complexitate n^2
  40. {
  41.     int i,j;
  42.     struct interval aux;
  43.  
  44.     for (i=0; i<n; i++)
  45.         for (j=i+1; j<n; j++)
  46.             if (v[i].deadline > v[j].deadline)
  47.                 {
  48.                     aux = v[i];
  49.                     v[i] = v[j];
  50.                     v[j] = aux;
  51.                 }
  52.  
  53. }
  54.  
  55. int comparator(const void *s1, const void *s2) //asta e pentru quicksort
  56. {
  57.     struct interval *e1 = (struct interval *) s1;
  58.     struct interval *e2 = (struct interval *) s2;
  59.  
  60.     //return e1->deadline - e2->deadline;
  61.  
  62.     if (e1->deadline > e2->deadline)
  63.         return 1;
  64.     else if (e1->deadline < e2->deadline)
  65.         return -1;
  66.     else
  67.         return e1->time - e2->time;
  68.  
  69.     return 0;
  70. }
  71.  
  72. void greedy(FILE *fout, int n, struct interval *v)
  73. {
  74.     fprintf(fout,"\n********************************************************\nRezolvare:\n");
  75.  
  76.     int i, lb = 0, hb, delay;
  77.  
  78.     for (i=0; i<n; i++)
  79.     {
  80.         hb = lb + v[i].time;
  81.  
  82.         fprintf(fout,"activitatea %d in intervalul [%d,%d) - intarziere %d\n",v[i].id, lb, hb, hb - v[i].deadline);
  83.  
  84.         lb = lb + v[i].time;
  85.     }
  86.  
  87. }
  88.  
  89. int main()
  90. {
  91.     FILE *fin, *fout;
  92.  
  93.     fin = fopen("date.in","r");
  94.     fout = fopen("date.out","w");
  95.  
  96.     struct interval vec[100];
  97.     int n;
  98.  
  99.     citire(fin,&n,vec);
  100.     qsort(vec,n,sizeof(struct interval),comparator);
  101.     afisare(fout,n,vec);
  102.     greedy(fout,n,vec);
  103.  
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment