问题 3686 --整数区间

3686: 整数区间

时间限制: 1 Sec  内存限制: 256 MB
提交: 10  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

我们定义一个整数区间[a,b]:是一个从a开始至b 结束的连续整数的集合。编一个程序,对给定的 n(n≤1000 )个区间,找出满足下述条件的所含元素个数最少的集合中元素的个数:对于所给定的每一个区间,都至少有两个不同的整数属于该集合。

题意:定义一个集合,每个区间的整数中,至少有两个不同整数在集合中。满足这个条件的集合中元素个数最小的集合。求这个集合的元素个数。

注意区分:区间和集合的概念。

输入

首行包括区间的数目n,

接下来的n 行,每行包括两个整数a,b,被一空格隔开,0<=a<b<=10000,它们是某一个区间的开始值和结束值。

输出

一个整数,表示最小的集合的元素个数

样例输入

4
3 6
2 4
0 2
4 7

样例输出

4

提示


1<=n<=10000



0<=a<b<10000

来源

[提交][状态]