Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- // Структура взята из нашего дерева сортировки
- 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 и b одновременно по началу отрезков
- heap_sort(a, N);
- heap_sort(b, N);
- int nonIntersectingCount = 0;
- int j = 0;
- for (int i = 0; i < N; ++i) {
- // Проверяем текущий отрезок с предыдущими отсортированными отрезками
- while (j < i && b[j] < a[i]) {
- j++;
- }
- if (j == i) {
- nonIntersectingCount++;
- }
- }
- cout << nonIntersectingCount << endl;
- delete[] a;
- delete[] b;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
