Advertisement
AlexandruDu

Problema Spectacolelor V1

Dec 8th, 2020
788
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. //Intr-o sală, trebuie planificate n spectacole care se vor desfășura într-o singură zi.
  2. Pentru fiecare spectacol se cunoaște intervalul orar în care se desfășoară, ora de inceput st, si ora de sfarsit sf. Se cere să se planifice un număr maxim de spectcole, astfel încât să nu se suprapună.
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. #define NMAX 100
  7. int n, k;
  8.  
  9. struct Time {
  10.     int h, mins;
  11.     bool operator < (const Time &other) const  {
  12.         if (h == other.h)
  13.             return mins < other.mins;
  14.         return h < other.h;
  15.     }
  16. };
  17.  
  18. struct Spectacol {
  19.     Time st, sf;
  20.     bool operator < (const Spectacol &other) const {
  21.         return sf < other.sf;
  22.     }
  23. } vs[NMAX], sol[NMAX];
  24.  
  25. void read() {
  26.     cin >> n;
  27.     for (int i = 1; i <= n; i++) {
  28.         cin >> vs[i].st.h >> vs[i].st.mins;
  29.         cin >> vs[i].sf.h >> vs[i].sf.mins;
  30.     }
  31. }
  32.  
  33. void greedy() {
  34.     sol[++k] = vs[1];
  35.     int j = 1;
  36.     for (int i = 2; i <= n; i++) {
  37.         if (vs[j].sf < vs[i].st) {
  38.             sol[++k] = vs[i];
  39.             j = i;
  40.         }
  41.     }
  42. }
  43.  
  44. void display(Spectacol v[]) {
  45.     for (int i = 1; i <= k; i++) {
  46.         cout << "spectacol " << i << " programat de la " << v[i].st.h<< ':' << v[i].st.mins << " la ";
  47.         cout << v[i].sf.h << ':' << v[i].sf.mins << endl;
  48.     }
  49. }
  50.  
  51. int main() {
  52.     read();
  53.     sort(vs + 1, vs + n + 1);//sortez crescator dupa ora de sfarsit
  54.     greedy();
  55.     display(sol);
  56.     return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement