2846 - 安全机器人

题目描述

某公司的物资仓库分布在一条笔直的运输线两侧,为了保障物资安全,公司计划派出 N 个安全机器人进行巡视。

每个机器人都有固定的巡视范围,第 i 个机器人的巡视范围表示为一个闭区间 [S_i, E_i]

为了防止机器人发生碰撞,任何两个机器人的巡视范围不能有重叠,即:第 i 个机器人和第 j 个机器人的巡视范围需满足 E_i \le S_j 或者 E_j \le S_i

你的任务是计算,在满足所有机器人巡视范围互不重叠的前提下最多可以安排多少个机器人同时进行巡视。

输入

第一行包含一个整数 N,表示安全机器人的数量。

接下来的 N 行,每行包含两个整数 S_iE_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
说明

样例 1 解释

一个满足题意的选择方案为,选择第 2 个机器人和第 4 个机器人,他们的巡视范围分别为 [2,5][6,10],显然是没有重叠的。

数据范围

40\% 的测试数据,满足 1 \le N \le 100

所有的测试点,满足 1 \leq N \leq 5 \times 10^41 \leq S_i < E_i \leq 10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 1 枚
难度 基础


上一题 下一题