work4/work_4.2/task3.cpp - develop - novd7/algirithms_sem2

work4/work_4.2/task3.cpp

96 строк2 KB

Новиков Владимир

Рабочая тетрадь 4.2

30 май 2026, 14:10

30 май 2026, 14:100a353cb

#include <algorithm>
#include <iostream>
#include <vector>

class MinHeap {
 private:
  std::vector<int> data;

  void siftUp(int index) {
    while (index > 0) {
      int parent = (index - 1) / 2;
      if (data[index] >= data[parent]) break;
      std::swap(data[index], data[parent]);
      index = parent;
    }
  }

  void siftDown(int index) {
    int size = data.size();
    while (true) {
      int left = 2 * index + 1;
      int right = 2 * index + 2;
      int smallest = index;

      if (left < size && data[left] < data[smallest]) {
        smallest = left;
      }
      if (right < size && data[right] < data[smallest]) {
        smallest = right;
      }

      if (smallest == index) break;

      std::swap(data[index], data[smallest]);
      index = smallest;
    }
  }

 public:
  void push(int value) {
    data.push_back(value);
    siftUp(data.size() - 1);
  }

  int top() const {
    if (data.empty()) return -1;
    return data[0];
  }

  void pop() {
    if (data.empty()) return;
    data[0] = data.back();
    data.pop_back();
    if (!data.empty()) {
      siftDown(0);
    }
  }

  bool empty() const { return data.empty(); }

  int size() const { return data.size(); }
};

int minClassrooms(std::vector<std::pair<int, int>>& exams) {
  std::sort(exams.begin(), exams.end());

  MinHeap minHeap;

  for (const auto& exam : exams) {
    int start = exam.first;
    int end = exam.second;

    if (!minHeap.empty() && minHeap.top() <= start) {
      minHeap.pop();
    }

    minHeap.push(end);
  }

  return minHeap.size();
}

int main() {
  int n;
  std::cin >> n;

  std::vector<std::pair<int, int>> exams(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> exams[i].first >> exams[i].second;
  }

  int result = minClassrooms(exams);
  std::cout << result << std::endl;

  return 0;
}