2824 - 会议安排

题目描述

A 公司多媒体会议室可以同时容纳 2 个小组开会。

会议室接到了公司 N 个不同小组的会议预约,每个会议预约都提交了会议的开始时间和结束时间。

如果第 i 个会议在时间 T_i 结束,第 j 个会议在 \ge Ti 的时间开始,认为这两个会议的时间是互不冲突的。

比如,某会议的开会时间将于 0 时开始, 3 时结束;另一个会议将于 3 时开始, 10 时结束,那么这两个会议互不冲突。

作为多媒体会议室的管理人员,请编程计算出,公司的多媒体会议室,最多可以安排多少个互不冲突的会议。

输入

1 行读入整数 N,代表申请会议的数量。

接下来的 N 行,每行有 2 个整数,代表了每个会议申请的开始时间和结束时间。

输出

输出 1 个整数,代表最多可以安排会议的数量。

样例

输入

5
7 14
9 14
5 7
8 10
4 13

输出

3

输入

9
2 14
6 13
5 6
5 15
8 15
7 12
0 5
3 6
8 13

输出

5

输入

6
0 3
6 7
3 10
1 5
2 8
1 9

输出

4
说明

【数据范围】

对于 30\% 的数据, 1 \le N \le 100

对于 100\% 数据,1 \le N \le 10^5,会议的起止时间在 [0,10^6] 范围内,并保证每个会议申请的开始时间 begin_i 严格小于会议的结束时间 end_i

来源

月赛

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


上一题 下一题