woolgatherer

Two Professors

Oct 7th, 2021
46
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define fastio  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  3. #define print(v) for(auto it : v) cout << it << ' '; cout << endl;
  4. #define valid(i, j, n, m) (i >= 1 && i <= n && j >= 1 && j <= m)
  5. #define all(x) (x).begin(), (x).end()
  6. #define debug(x) cout << #x << "--> " << x << endl;
  7. #define int long long
  8. #define pii pair<int, int>
  9. #define ppii pair<pii, int>
  10. #define fi first
  11. #define se second
  12. #define inf 1e18
  13. using namespace std;
  14.  
  15. const int mod = 1e6 + 7;
  16. const int N = 2e5 + 5;
  17.  
  18. struct Interval
  19. {
  20.     int tval, type, id;
  21.     Interval(int _tval, int _type, int _id)
  22.     {
  23.         tval = _tval;
  24.         type = _type;
  25.         id = _id;
  26.     }
  27.     bool operator<(Interval const & A) const
  28.     {
  29.         if (tval != A.tval) return tval < A.tval;
  30.         else  return type > A.type;
  31.     }
  32. };
  33. main()
  34. {
  35. #ifndef ONLINE_JUDGE
  36.     freopen("input1.txt", "r", stdin);
  37.     freopen("output1.txt", "w", stdout);
  38. #endif
  39.     int tc; cin >> tc;
  40.     while (tc--)
  41.     {
  42.         int n; cin >> n;
  43.         vector<Interval>vec;
  44.         for (int i = 1; i <= n; i++)
  45.         {
  46.             int st; cin >> st;
  47.             int ed; cin >> ed;
  48.             vec.push_back(Interval(st, 1, i));
  49.             vec.push_back(Interval(ed, 2, i));
  50.         }
  51.  
  52.         if (vec[0].tval > vec[2].tval)
  53.         {
  54.             vec[0].id = 2, vec[2].id = 1;
  55.             vec[1].id = 2, vec[3].id = 1;
  56.         }
  57.  
  58.         sort(vec.begin(), vec.end());
  59.         deque<int>available;
  60.         int rooms[n + 1], rnum = 0;
  61.         for (int i = 0; i < vec.size(); i++)
  62.         {
  63.             int type = vec[i].type;
  64.             int id = vec[i].id;
  65.  
  66.             if (type == 1)
  67.             {
  68.                 if (available.empty() == false)
  69.                 {
  70.                     if (id == 2)
  71.                     {
  72.                         if (available.size() == 1) // only one free rooms are there
  73.                         {
  74.                             int freeRoom = available.front();
  75.                             if (rooms[1] == freeRoom)
  76.                             {
  77.                                 ++rnum;
  78.                                 rooms[2] = rnum;
  79.                             }
  80.                             else
  81.                             {
  82.                                 rooms[2] = freeRoom;
  83.                                 available.pop_front();
  84.                             }
  85.                             continue;
  86.                         }
  87.  
  88.                         // more than 1 free rooms
  89.                         int freeRoom1 = available.front();
  90.                         int freeRoom2 = available.back();
  91.  
  92.                         if (rooms[1] == freeRoom1) // if freeRoom1 is the room where meeting 1 held
  93.                         {
  94.                             rooms[2] = freeRoom2; // host it in the second free room
  95.                             available.pop_back();
  96.                         }
  97.                         else // else you can safely held meeting 2 in freeRoom1
  98.                         {
  99.                             rooms[2] = freeRoom1;
  100.                             available.pop_front();
  101.                         }
  102.                     }
  103.                     else
  104.                     {
  105.                         rooms[id] = available.front();
  106.                         available.pop_front();
  107.                     }
  108.                 }
  109.                 else
  110.                 {
  111.                     // if no free rooms are there you have no other option without allocating a new room
  112.                     rnum++;
  113.                     rooms[id] = rnum;
  114.                 }
  115.             }
  116.             else
  117.             {
  118.                 int Allocated_Room = rooms[id];
  119.                 available.push_back(Allocated_Room);
  120.             }
  121.         }
  122.         cout << rnum << endl;
  123.         // for (int i = 1; i <= n; i++) cout << rooms[i] << ' ';
  124.         // cout << endl;
  125.     }
  126. }
  127.  
  128.  
RAW Paste Data