普及-⏱ 1000ms💾 256MB#P3176🏷️ 排序贪心

题目描述

一段河岸上布设了 $n$ 个监测任务,第 $i$ 个任务负责的河段用整数桩号区间 $[a_i, b_i]$ 描述。 一个测温桩可以同时服务所有覆盖它桩号的监测任务。

请选一个包含元素最少的整数桩号集合,使得每个区间 $[a_i, b_i]$ 内都至少有集合中的一个桩号, 输出集合的元素个数。

输入格式

第一行一个整数 $n$; 接下来 $n$ 行,每行两个整数 $a_i, b_i$($a_i \le b_i$),表示一个闭区间。

输出格式

一行,一个整数:满足要求的桩号集合的最少元素个数。

数据范围

$$1 \le n \le 10^4,\quad 0 \le a_i \le b_i \le 10^4$$

样例输入 #1
4
3 6
2 4
0 2
4 7
样例输出 #1
2
样例输入 #2
1
0 0
样例输出 #2
1