某公司的物资仓库分布在一条笔直的运输线两侧,为了保障物资安全,公司计划派出 N 个安全机器人进行巡视。
每个机器人都有固定的巡视范围,第 i 个机器人的巡视范围表示为一个闭区间 [S_i, E_i]。
为了防止机器人发生碰撞,任何两个机器人的巡视范围不能有重叠,即:第 i 个机器人和第 j 个机器人的巡视范围需满足 E_i \le S_j 或者 E_j \le S_i。
你的任务是计算,在满足所有机器人巡视范围互不重叠的前提下,最多可以安排多少个机器人同时进行巡视。
第一行包含一个整数 N,表示安全机器人的数量。
接下来的 N 行,每行包含两个整数 S_i 和 E_i,表示第 i 个机器人的巡视范围的起始点和终止点。
输出一个整数,表示最多可以同时安排的安全机器人数量。
7 9 14 2 5 2 14 6 10 6 12 6 15 9 15
2
18 54 73 26 77 26 98 8 58 15 39 32 76 54 78 32 45 36 66 65 96 20 63 29 53 31 36 10 23 18 94 62 69 12 82 47 100
3
30 1931 3167 188 2851 1335 2376 1216 4094 204 1903 183 2912 946 1075 4 1753 3759 4222 2374 4112 141 4304 3014 4037 77 3124 2235 4750 2514 4535 3105 3582 1245 4822 84 4329 1721 4498 2287 4361 4037 4222 1796 3848 684 1495 1557 2965 1955 2801 2129 4506 219 2745 3439 4255 2710 4742 430 1691
4
一个满足题意的选择方案为,选择第 2 个机器人和第 4 个机器人,他们的巡视范围分别为 [2,5]、[6,10],显然是没有重叠的。
有 40\% 的测试数据,满足 1 \le N \le 100。
所有的测试点,满足 1 \leq N \leq 5 \times 10^4,1 \leq S_i < E_i \leq 10^9。