#YHSP4003. 会议安排

会议安排

题目:会议安排

题目描述

A 公司多媒体会议室可同时容纳 2 个小组开会。收到 N N 个小组的会议预约,每个预约有开始和结束时间。若第 i i 个会议在 Ti T_i 结束,第 j j 个会议在 Ti \geq T_i 开始,则两会议不冲突。需计算最多可安排的互不冲突会议数量。

输入格式

  • 第 1 行:整数 N N ,代表申请会议的数量。
  • 接下来 N N 行:每行两个整数,为每个会议申请的开始时间和结束时间(开始时间严格小于结束时间 )。

输出格式

输出一个整数,为最多可安排的会议数量。

样例

  • 输入示例 1
5
7 14
9 14
5 7
8 10
4 13
  • 输出示例 1
3
  • 输入示例 2
9
2 14
6 13
5 6
5 15
8 15
7 12
0 5
3 6
8 13
  • 输出示例 2
5
  • 输入示例 3
6
0 3
6 7
3 10
1 5
2 8
1 9
  • 输出示例 3
4

数据范围

  • 30% 数据:1N100 1 \leq N \leq 100
  • 100% 数据:1N105 1 \leq N \leq 10^5 ,会议起止时间在 [0,106][0, 10^6] 范围内,且每个会议开始时间严格小于结束时间 。