Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- // Попытка 3: теперь чуть более осмысленно ходим по отрезкам!
- // Та же структура у функций
- void swap(int &a, int &b) {
- int temp = a;
- a = b;
- b = temp;
- }
- void sift_down(int* heap, int size, int index) {
- while (2 * index + 1 < size) {
- int j = 2 * index + 1;
- if (j + 1 < size && heap[j] < heap[j + 1]) j++;
- if (heap[index] >= heap[j]) break;
- swap(heap[index], heap[j]);
- index = j;
- }
- }
- void build_heap(int* array, int size) {
- for (int i = size / 2 - 1; i >= 0; --i) {
- sift_down(array, size, i);
- }
- }
- void heap_sort(int* array, int size) {
- build_heap(array, size);
- for (int i = size - 1; i > 0; --i) {
- swap(array[0], array[i]);
- sift_down(array, i, 0);
- }
- }
- int main() {
- int N;
- cin >> N;
- int* a = new int[N];
- int* b = new int[N];
- for (int i = 0; i < N; ++i) {
- cin >> a[i] >> b[i];
- }
- // Сортируем массив a по началу отрезков
- heap_sort(a, N);
- // Сортируем массив b по возрастанию концов отрезков
- heap_sort(b, N);
- int nonIntersectingCount = 0;
- int endIndex = 0;
- for (int i = 0; i < N; ++i) {
- // Пропускаем все отрезки, которые закончились до начала текущего отрезка
- while (endIndex < N && b[endIndex] < a[i]) {
- endIndex++;
- }
- // Если текущий отрезок не пересекается ни с одним предыдущим, увеличиваем счетчик
- if (endIndex == i) {
- nonIntersectingCount++;
- }
- }
- cout << nonIntersectingCount << endl;
- delete[] a;
- delete[] b;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
