HA18_O(N)

#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;
}