Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <vector>
- using std::cout;
- using std::endl;
- using std::cin;
- struct Time {
- int arrival_time;
- int departure_time;
- Time() : arrival_time(0), departure_time(0) {}
- };
- template <class T>
- class Heap {
- private:
- std::vector<T> buffer;
- void BuildHeap();
- void SiftDown(int index);
- void SiftUp(int index);
- int count;
- public:
- Heap();
- ~Heap();
- int ExtractMax();
- void Push(const T& value);
- int GetCount();
- int TopHeap();
- bool IsNotEmpty();
- };
- template <class T>
- Heap<T>::Heap()
- {
- count = 0;
- BuildHeap();
- }
- template <class T>
- Heap<T>::~Heap() {}
- template <class T>
- void Heap<T>::SiftDown(int index)
- {
- int i = 0;
- for (i; i * 2 + 2 < buffer.size(); ) {
- if (buffer[i * 2 + 1] > buffer[i * 2 + 2]) {
- if (buffer[i * 2 + 1] > buffer[i]) {
- std::swap(buffer[i * 2 + 1], buffer[i]);
- i = i * 2 + 1;
- }
- else
- break;
- }
- else {
- if (buffer[i * 2 + 2] > buffer[i]) {
- std::swap(buffer[i * 2 + 2], buffer[i]);
- i = i * 2 + 2;
- }
- else
- break;
- }
- }
- if (i * 2 + 1 < buffer.size())
- if (buffer[i * 2 + 1]>buffer[i])
- std::swap(buffer[i * 2 + 1], buffer[i]);
- }
- template <class T>
- void Heap<T>::SiftUp(int index)
- {
- int parrent = 0;
- while (index > 0) {
- parrent = (index - 1) / 2;
- if (buffer[index] > buffer[parrent]) {
- std::swap(buffer[index], buffer[parrent]);
- }
- else
- return;
- index = parrent;
- }
- }
- template <class T>
- void Heap<T>::Push(const T& value)
- {
- buffer.push_back(value);
- SiftUp(count);
- ++count;
- }
- template <class T>
- int Heap<T>::ExtractMax()
- {
- assert(!buffer.empty());
- int max = buffer[0];
- buffer[0] = buffer[count - 1];
- buffer.pop_back();
- SiftDown(0);
- --count;
- return max;
- }
- template <class T>
- void Heap<T>::BuildHeap()
- {
- for (int i = buffer.size() / 2 - 1; i >= 0; --i) {
- SiftDown(i);
- }
- }
- template <class T>
- int Heap<T>::GetCount()
- {
- return count;
- }
- template <class T>
- int Heap<T>::TopHeap()
- {
- return buffer[0];
- }
- template <class T>
- bool Heap<T>::IsNotEmpty()
- {
- return count > 0;
- }
- void EnterData(Time& obj)
- {
- cin >> obj.arrival_time >> obj.departure_time;
- assert(obj.arrival_time >= 0 && obj.arrival_time <= 1000000000);
- assert(obj.departure_time >= 0 && obj.departure_time <= 1000000000);
- }
- int main() {
- Heap<int> heap;
- std::vector<int> buff;
- int p = 0;
- int n = 0;
- Time time;
- int count = 0;
- cin >> n;
- assert(n > 0);
- for (int i = 0; i < n; ++i) {
- EnterData(time);
- if (heap.IsNotEmpty()) {
- while (heap.IsNotEmpty() && time.arrival_time <= heap.TopHeap()) {
- buff.push_back(heap.ExtractMax());
- ++count;
- }
- if (heap.IsNotEmpty() && time.arrival_time > heap.TopHeap()) {
- heap.ExtractMax();
- for (int j = buff.size() - 1; j >= 0; --j) {
- heap.Push(buff[j]);
- buff.pop_back();
- }
- }
- if (!heap.IsNotEmpty()) {
- for (int j = buff.size() - 1; j >= 0; --j) {
- heap.Push(buff[j]);
- buff.pop_back();
- }
- }
- }
- heap.Push(time.departure_time);
- }
- cout << heap.GetCount();
- cout << endl;
- system("pause");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement