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];
- }
- heap_sort(a, N);
- heap_sort(b, N);
- int nonIntersectingCount = 0;
- int maxEnd = b[0]; // Теперь вместо нуля храним первое значение массива
- // Проход по массиву начала отрезков
- for (int i = 0; i < N; ++i) {
- // Проверяем текущее начало отрезка
- if (a[i] > maxEnd) {
- nonIntersectingCount++;
- }
- // Обновляем максимальное значение конца отрезка
- maxEnd = max(maxEnd, b[i]);
- }
- cout << nonIntersectingCount << endl;
- delete[] a;
- delete[] b;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
