问题1705--小西的区间问题

1705: 小西的区间问题

[命题人 : ]
时间限制 : 1 sec  内存限制 : 256 MB

提交

题目描述

        小西最近被一个关于区间的问题难到了,他得到了N段区间,每段区间都有左右端点l,r(1≤l≤r≤109)。
        小西现在需要从N段区间里面取尽可能多段区间,满足取出的区间段里存在一段区间和剩下所有取出的区间段都相交,换言之当取出x段区间后,存在一个区间和剩下的x−1段区间都相交。
        如果两段区间存在至少一个公共点,我们就称这两段区间是相交的。

输入

        第一行输入一个正整数N(1≤N≤2×105)。接下来的N行,每行两个正整数l,r(1≤l≤r≤109)

输出

        输出一个正整数,表示小西最多能取出的区间数。

样例输入 Copy

3
1 4
2 3
3 6

样例输出 Copy

3