<ПРЕД Задача:
СЛЕД>
Задачу решили 48 пользователей: Evgeny, Pupyrev, marian, NSI, Shurik, naum, LPN_3, programer, Jarovit, yangzhe1990, Elwin, wojtekt, tomek, szywrz, venkatkenshi, zmy, relja, Cheryl, RAVEman, rvashegin, WsemirZ, obtuseSword, littleboy, pmnox, defrager, UdH-WiNGeR, regal, Al.Cash, vitar, Quazar, vi002, tourist, mathematic, JohnJones_001, Kuznetsov_S, LiuChenheng, Dest, Jacob, opsupwow, NIGHTFIT, Azizkhan, Robert_Gerbicz, regmar, murphy, Ramazan_S, adamant, Chmeli_BSU, avg79.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Интервалы

Time limit = 5 секунд(ы)

Memory limit = 64 Mb

Задано N интервалов (a_i, b_i) , a_i < b_i, на прямой.

Числа a_i и b_i целые и не превосходят по модудю 2'000'000'000.

Требуется найти число способов выбрать из них максимальное множество непресекающихся интревалов. Интервалы могут совпадать, но при этом они считаются разными (интервалы — это бозоны, а не фермионы).

Вход В первой строке N (1 ≤ N ≤ 100000) Cледующие N строк содержат координаты концов интервалов. В каждой строке записано два числа a_i и b_i, разделённых пробелом.

Выход Нужно вывести единственное число — искомое число способов. Известно, что это оно не превосходит 10^18

Вход#1
4
1 2
1 4
3 5
4 5
Выход#1
3

Вход#2
4
1 2
1 2
2 3
2 3
Выход#2
4

Автор:
Жук Сергей, IV Физтех олимпиада
11 апреля 2004

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 35.172.195.82