‹ 上一题 下一题 ›

g5-09045. 社团活动安排 未做

1000 ms 256 MB 测试点 10 通过率 50% GESP-55级·贪心经典模型区间调度与选择阶梯·0

题目描述

学校只有一间活动室。学期初收到 份社团申请,第 份申请希望从第 小时开始使用,到第 小时结束。同一时刻活动室只能给一个社团使用;一个社团结束的时刻,下一个社团可以立刻开始。

最多能批准多少份申请,使它们互不冲突?

输入格式

第一行一个整数 。接下来 行,每行两个整数 。

输出格式

一行一个整数:最多能批准的申请数。

样例

输入
5
1 3
2 5
4 7
6 8
8 10
输出
3

样例解释

批准第 份(、、):前一份的结束时刻正好是后一份的开始时刻,可以衔接,共 份。若批准第 份(),它和第 份都冲突,最多只能再配第 份,只有 份,不如 份多。

数据范围

,。

输入
输出

            
答案