Задача Яндекса.

Дается N пар чисел a_i, b_i.
Вы строите N отрезков, где концы i-того отрезка находятся в (a_i, 0) и (1, b_i).
Найти количество отрезков этого множества, которые не пересекаются с другими отрезками.

Например
a = [1, 2, 3, 4, 5]
b = [4, 5, 1, 5, 6]
Ответ 1
Только последний отрезок не пересекается.

Решение:
Давайте отсортируем отрезке по координате a_i.
Теперь подумаем, когда отрезок (a_i, 0), (1, b_i) пересекается с другим отрезком j.
У нас два варианта пересечения
1) a_j <= a_i and b_j >= b_i
2) a_j >= a_i and b_j <= b_i

Пусть мы в i-той позиции, так как мы отсортировали все по a нас интересует максимальный b_j. Максимальный b_j можно хранить в отдельной переменной во время обхода обновляя. Таким образом мы должны просто проверить правда ли max_b >= b_i.

Аналогично давайте пройдемся справа налево, но уже будем хранить минимальный b справа. Для каждой позиции i проверяем min_b <= b_i.

Асимптотика O(N logN).

Код в комментариях.