描述
给定 $ N $ 个闭区间 $([a_i, b_i])$,请你在数轴上选择尽可能少的点,使得每个区间内至少包含一个选出的点(包括端点)。
输出所需点的最小数量。
输入
- 第一行包含一个整数 $ N ( 1 \le N \le 10^5 )$,表示区间的个数。
- 接下来 $ N $ 行,每行包含两个整数 $ a_i $ 和 $ b_i ( -10^9 \le a_i \le b_i \le 10^9 )$,表示第 $ i $ 个区间的左右端点。
输出
输出一个整数,表示所需的最少点数。
样例
- 复制
- 复制
提示
## 数据范围与约定
- $ 1 \le N \le 10^5 $
- $ -10^9 \le a_i \le b_i \le 10^9 $

关注我们