/ Vijos / 题库 /

区间选点

区间选点

时间限制:1秒  内存限制:256M


【问题描述】

  数轴上有 \(n\) 个闭区间 \([a_i,b_i]\)。请选择尽量少的点,使得每个区间内都至少有一个你选择的点。

【输入格式】

  第 1 行一个整数 \(n\),表示闭区间数目。
  接下来的 \(n\) 行,每行包括两个整数 \(a_i,b_i\),被一空格隔开,表示一个闭区间。

【输出格式】

  一个整数,表示最少点数目。

【输入输出样例】

 Input

4
3 6
2 4
0 2
4 7

 Output

2

【数据规模与约定】

  \(1 ≤ n ≤ 10000\)
  \(0 ≤ a_i ≤ b_i ≤ 10^7\)

【来源】

  Mr.he

信息

ID
1131
难度
3
分类
贪心 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
4
上传者