区间选点

题目描述

给定 $N$ 个闭区间 $[l,r]$，请在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出所选点的最小数量。

注意：位于区间端点上的点也算作区间内。

输入格式

第一行一个整数 $N$（$1 \le N \le 10^5$），表示闭区间数量。

接下来 $N$ 行，每行两个整数 $l$，$r$，分别表示一个区间的左端点和右端点（$-10^9 \le l \le r \le 10^9$）。

输出格式

输出一个整数，表示所选点的最小数量。

样例输入 #1

5
0 3
1 2
-1 2
0 1
4 5

样例输出 #1

2

数据范围

$1 \le N \le 10^5$

$-10^9 \le l \le r \le 10^9$

知识点与难度

本题涉及的知识点从属于 GESP五级（贪心），难度等级：⭐⭐⭐。

测试点分布