普及-⏱ 1000ms💾 256MB#P3085

题目描述

数轴上有 $n$ 个闭区间,要求选出最少的点,使每个区间至少包含一个选中的点。输出最少点数。(经典结论:按右端点排序后贪心选取右端点。)

输入格式

第一行整数 $n$;接下来 $n$ 行每行两个整数 $l, r$

输出格式

一行一个整数。

数据范围

$$1 \le n \le 10^5,\ 0 \le l \le r \le 10^9$$

样例输入 #1
1
0 1000000000
样例输出 #1
1
样例输入 #2
2
1 3
3 5
样例输出 #2
2