icatalin

intervale greedy nu stiu sigur

Apr 27th, 2018
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.57 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct interval
  5. {
  6.     int low, high;
  7. };
  8.  
  9. void citire(FILE *fin, int *n, int *a, int *b, struct interval *ptr)
  10. {
  11.     fscanf(fin,"%d",&(*a));
  12.     fscanf(fin,"%d",&(*b));
  13.     fscanf(fin,"%d",&(*n));
  14.  
  15.     int i;
  16.  
  17.     for (i=0; i<*n; i++)
  18.     {
  19.         fscanf(fin,"%d %d",&ptr->low,&ptr->high);
  20.         ptr++;
  21.     }
  22.  
  23. }
  24.  
  25. void afisare(FILE *fout, int n, int a, int b, struct interval *ptr)
  26. {
  27.     fprintf(fout,"Vector sortat crescator dupa high:\n");
  28.  
  29.     int i;
  30.  
  31.     fprintf(fout,"Intervalul [%d,%d]\n",a,b);
  32.  
  33.     fprintf(fout,"%d\n",n);
  34.  
  35.     for (i=0; i<n; i++)
  36.     {
  37.         fprintf(fout,"%d %d \n", ptr->low, ptr->high);
  38.         ptr++;
  39.     }
  40.  
  41. }
  42.  
  43. int comparator(const void *s1, const void *s2) //asta e pentru quicksort
  44. {
  45.     struct interval *e1 = (struct interval *) s1;
  46.     struct interval *e2 = (struct interval *) s2;
  47.  
  48.     return e1->high - e2->high;
  49. }
  50.  
  51. void greedy(FILE *fout, int n, int a, int b, struct interval *v)
  52. {
  53.     fprintf(fout,"\n********************************************************\nRezolvare:\n");
  54.  
  55.     int i=0, low_aux, high_aux;
  56.  
  57.     while (a <= b)
  58.     {
  59.         while (v[i].low <= a && v[i].high > a && i<n)
  60.         {
  61.             low_aux = v[i].low;
  62.             high_aux = v[i].high;
  63.             i++;
  64.         }
  65.         a = high_aux;
  66.         fprintf(fout,"%d %d\n",low_aux,high_aux);
  67.     }
  68.  
  69. }
  70.  
  71. int main()
  72. {
  73.     FILE *fin, *fout;
  74.  
  75.     fin = fopen("date.in","r");
  76.     fout = fopen("date.out","w");
  77.  
  78.     struct interval vec[100];
  79.     int n,a,b;
  80.  
  81.     citire(fin,&n,&a,&b,vec);
  82.     qsort(vec,n,sizeof(struct interval),comparator);
  83.     afisare(fout,n,a,b,vec);
  84.     greedy(fout,n,a,b,vec);
  85.  
  86.     return 0;
  87. }
  88.  
  89. //cod luat
  90. #include <stdio.h>
  91. #include <stdlib.h>
  92. struct Interval
  93. {
  94.     int a,b;
  95. };
  96. int cmp (const void *p, const void *q)
  97. {
  98.     struct Interval vp = *(struct Interval *)p;
  99.     struct Interval vq = *(struct Interval *)q;
  100.     return vp.b - vq.b;
  101. }
  102.  
  103. int main()
  104. {
  105.     int n , i, A, B, aaux, baux;
  106.     printf("n="); scanf("%d", &n);
  107.     printf("A="); scanf("%d", &A);
  108.     printf("B="); scanf("%d", &B);
  109.     printf("Intervalele: ");
  110.     struct Interval v[100];
  111.     for(i = 0; i < n; i++)
  112.         scanf("%d%d", &v[i].a, &v[i].b);
  113.     qsort (v, n, sizeof(struct Interval), cmp);
  114.     i=0;
  115.     while (A <=B)
  116.     {
  117.         while (v[i].a <= A && v[i].b > A && i<n)
  118.             {
  119.                 aaux = v[i].a;
  120.                 baux = v[i].b;
  121.                 i++;
  122.             }
  123.         A=baux;
  124.         printf("[%d,%d]\n", aaux, baux);
  125.     }
  126.  
  127.     return 0;
  128. }
Add Comment
Please, Sign In to add comment