/ Vijos / 题库 /

区间

区间

描述

给你n个边界是整数的闭区间[ai,bi],每个区间表示的范围是ai到bi范围内的连续的整数。

请你找到一个整数集合Z,使得:
1、|Z|最小。即集合z内的整数个数最小。

2、z∩[ai,bi]>=2。 即z和每个集合至少有两个相交的不同整数。

格式

输入格式

第一行:n(1<=n<=10000),表示整数区间的个数。

以下n行,每行两个数a和b,中间一个空格隔开,表示一个区间,0 <= a < b <= 10000。

输出格式

一个正整数,z的个数。

样例1

样例输入1

4
3 6
2 4
0 2
4 7

样例输出1

4

限制

每个测试点1s

信息

ID
1444
难度
5
分类
贪心 点击显示
标签
(无)
递交数
728
已通过
241
通过率
33%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

NOIP代码+思维