题目描述

有 $N$ 个安全机器人，第 $i$ 个机器人的巡视范围是闭区间 $[S_i,E_i]$。

为了避免碰撞，任意两个被安排的机器人，其巡视区间内部不能重叠。区间端点相接是允许的，即两个区间满足 $E_i \le S_j$ 或 $E_j \le S_i$ 时可以同时选择。

求最多可以安排多少个机器人同时巡视。

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含两个整数 $S_i,E_i$，表示一个机器人的巡视范围。

输出格式

输出一个整数，表示最多可以安排的机器人数量。

7
9 14
2 5
2 14
6 10
6 12
6 15
9 15

2

数据范围与提示

• 对于 $40\%$ 的数据，$1 \le N \le 100$
• 对于全部数据，$1 \le N \le 5 \times 10^4$
• $1 \le S_i < E_i \le 10^9$