<PREV Problem:
NEXT>
Solved by 48 users: 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.
UserDateAttemptTimeCMSC
tomek18 feb 2006C++500.20218 
Al.Cash04 aug 2009C++200.92277 
mathematic10 sep 2011C++400.17311 
adamant19 feb 2015C++700.87329 
Quazar29 jun 2011C++1001.09334 
Quazar29 jun 2011C++500.20338 
Quazar29 jun 2011C++800.19340 
marian01 nov 2004C++1?.??341 
NIGHTFIT27 mar 2012C++800.27355 
NIGHTFIT27 mar 2012C++700.27357 
obtuseSword05 may 2008C++101.03359 
JohnJones_00110 sep 2011C++400.23372 
szywrz18 feb 2006C++100.21374 
Languages
C++
35
Kylix
6
FPC
5
Java
3
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

Intervals

Time limit = 5 second(s)

Memory limit = 64 Mb

There are N intervals (a_i, b_i). a_i and b_i are integers not exceeding 2'000'000'000 by their absolute value.

Your task is to find the number of ways we could choose a maximum subset of disjoint intervals.

Input First line contains N (1 ≤ N ≤ 100000) In the next N lines coordinates of the ends of intervals are given. Each line contains two numbers a_i, b_i serarated with a space.

Output The only number — unknown number of ways. It's known it doesn't exceed 10^18.

Input#1
4
1 2
1 4
3 5
4 5
Output#1
3

Input#2
4
1 2
1 2
2 3
2 3
Output#2
4

Author:
Zhuk Sergey, IV MIPT Contest
11 April 2004

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 100.26.179.196