Advertisement
madalinaradu

ASD Pb 12 spectacole

May 26th, 2019
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. /**
  2. Problema programarii spectacolelor
  3. Intr-o sala de spectacol trebuie planificate n spectacole intr-o zi. Pentru fiecare spectacol se cunosc ora de inceput si ora de terminare (numere intregi).
  4. Sa se planifice un numar maxim de spectacole astfel inct sa nu fie doua spectacole care sa se suprapuna.
  5. Exemplu:
  6. spectacole.in
  7. 7
  8. 2 4
  9. 8 11
  10. 5 6
  11. 5 8
  12. 3 7
  13. 7 8
  14. 9 12
  15. spectacole.out:
  16. 2,4 5,6 7,8 9,12
  17.  
  18. */
  19. #include<fstream>
  20. using namespace std;
  21. ifstream fin("spectacole.in");
  22. ofstream fout("spectacole.out");
  23.  
  24. struct spectacol {
  25.     int start,sfarsit;
  26. };
  27.  
  28. void citire(int n, spectacol a[]) {
  29.     fin>>n;
  30.     for(int i=1; i<=n; i++)
  31.         fin>>a[i].start>>a[i].sfarsit;
  32. }
  33.  
  34. void ordonare(int n, spectacol a[]) {///ordonarea se face dupa sfarsitul spectacolelor
  35.     int i,j;
  36.     spectacol aux;
  37.     for(i=1; i<n; i++)
  38.         for(j=i+1; j<=n; j++)
  39.             if(a[i].sfarsit>a[j].sfarsit) {
  40.                 aux=a[i];
  41.                 a[i]=a[j];
  42.                 a[j]=aux;
  43.             }
  44. }
  45.  
  46. void afisare(int n, spectacol a[]) {
  47.     for(int i=1; i<=n; i++)
  48.         fout<<a[i].start<<","<<a[i].sfarsit<<endl;
  49. }
  50.  
  51. void greedy(int n, spectacol a[]) {
  52.     spectacol solutie[100];
  53.     int i,k;
  54.     k=1;
  55.     solutie[1]=a[1];
  56.     for(i=2; i<=n; i++)
  57.         if(solutie[k].sfarsit<a[i].start)
  58.             solutie[++k]=a[i];
  59.     afisare(k,solutie);
  60. }
  61.  
  62. int main() {
  63.     int n;
  64.     spectacol a[100];
  65.     citire(n,a);
  66.     ordonare(n,a);
  67.     greedy(n,a);
  68.     fin.close();
  69.     fout.close();
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement