Advertisement
Guest User

Untitled

a guest
Oct 16th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3. #include <vector>
  4.  
  5. using std::cout;
  6. using std::endl;
  7. using std::cin;
  8.  
  9. struct Time {
  10.     int arrival_time;
  11.     int departure_time;
  12.     Time() : arrival_time(0), departure_time(0) {}
  13. };
  14.  
  15. template <class T>
  16. class Heap {
  17. private:
  18.     std::vector<T> buffer;
  19.     void BuildHeap();
  20.     void SiftDown(int index);
  21.     void SiftUp(int index);
  22.     int count;
  23. public:
  24.     Heap();
  25.     ~Heap();
  26.  
  27.     int ExtractMax();
  28.     void Push(const T& value);
  29.     int GetCount();
  30.     int TopHeap();
  31.     bool IsNotEmpty();
  32.  
  33. };
  34.  
  35. template <class T>
  36. Heap<T>::Heap()
  37. {
  38.     count = 0;
  39.     BuildHeap();
  40. }
  41.  
  42. template <class T>
  43. Heap<T>::~Heap() {}
  44.  
  45. template <class T>
  46. void Heap<T>::SiftDown(int index)
  47. {
  48.  
  49.     int i = 0;
  50.     for (i; i * 2 + 2 < buffer.size(); ) {
  51.         if (buffer[i * 2 + 1] > buffer[i * 2 + 2]) {
  52.             if (buffer[i * 2 + 1] > buffer[i]) {
  53.                 std::swap(buffer[i * 2 + 1], buffer[i]);
  54.                 i = i * 2 + 1;
  55.             }
  56.             else
  57.                 break;
  58.         }
  59.         else {
  60.             if (buffer[i * 2 + 2] > buffer[i]) {
  61.                 std::swap(buffer[i * 2 + 2], buffer[i]);
  62.                 i = i * 2 + 2;
  63.             }
  64.             else
  65.                 break;
  66.         }
  67.     }
  68.     if (i * 2 + 1 < buffer.size())
  69.         if (buffer[i * 2 + 1]>buffer[i])
  70.             std::swap(buffer[i * 2 + 1], buffer[i]);
  71. }
  72.  
  73. template <class T>
  74. void Heap<T>::SiftUp(int index)
  75. {
  76.     int parrent = 0;
  77.     while (index > 0) {
  78.         parrent = (index - 1) / 2;
  79.         if (buffer[index] > buffer[parrent]) {
  80.             std::swap(buffer[index], buffer[parrent]);
  81.         }
  82.         else
  83.             return;
  84.         index = parrent;
  85.     }
  86. }
  87.  
  88. template <class T>
  89. void Heap<T>::Push(const T& value)
  90. {
  91.     buffer.push_back(value);
  92.     SiftUp(count);
  93.     ++count;
  94. }
  95.  
  96. template <class T>
  97. int Heap<T>::ExtractMax()
  98. {
  99.     assert(!buffer.empty());
  100.     int max = buffer[0];
  101.     buffer[0] = buffer[count - 1];
  102.     buffer.pop_back();
  103.     SiftDown(0);
  104.     --count;
  105.     return max;
  106. }
  107.  
  108. template <class T>
  109. void Heap<T>::BuildHeap()
  110. {
  111.     for (int i = buffer.size() / 2 - 1; i >= 0; --i) {
  112.         SiftDown(i);
  113.     }
  114. }
  115.  
  116. template <class T>
  117. int Heap<T>::GetCount()
  118. {
  119.     return count;
  120. }
  121.  
  122. template <class T>
  123. int Heap<T>::TopHeap()
  124. {
  125.     return buffer[0];
  126. }
  127.  
  128. template <class T>
  129. bool Heap<T>::IsNotEmpty()
  130. {
  131.     return count > 0;
  132. }
  133. void EnterData(Time& obj)
  134. {
  135.     cin >> obj.arrival_time >> obj.departure_time;
  136.     assert(obj.arrival_time >= 0 && obj.arrival_time <= 1000000000);
  137.     assert(obj.departure_time >= 0 && obj.departure_time <= 1000000000);
  138. }
  139.  
  140. int main() {
  141.     Heap<int> heap;
  142.     std::vector<int> buff;
  143.  
  144.     int p = 0;
  145.     int n = 0;
  146.     Time time;
  147.     int count = 0;
  148.     cin >> n;
  149.     assert(n > 0);
  150.     for (int i = 0; i < n; ++i) {
  151.         EnterData(time);
  152.         if (heap.IsNotEmpty()) {
  153.             while (heap.IsNotEmpty() && time.arrival_time <= heap.TopHeap()) {
  154.                 buff.push_back(heap.ExtractMax());
  155.                 ++count;
  156.             }
  157.             if (heap.IsNotEmpty() && time.arrival_time > heap.TopHeap()) {
  158.                 heap.ExtractMax();
  159.                 for (int j = buff.size() - 1; j >= 0; --j) {
  160.                     heap.Push(buff[j]);
  161.                     buff.pop_back();
  162.                 }
  163.             }
  164.             if (!heap.IsNotEmpty()) {
  165.                 for (int j = buff.size() - 1; j >= 0; --j) {
  166.                     heap.Push(buff[j]);
  167.                     buff.pop_back();
  168.                 }
  169.             }
  170.         }
  171.  
  172.         heap.Push(time.departure_time);
  173.     }
  174.     cout << heap.GetCount();
  175.     cout << endl;
  176.    
  177.     system("pause");
  178.     return 0;
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement