‹ 上一题 下一题 ›

g5-09050. 兴趣班教室 未做

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

题目描述

少年宫开了 个兴趣班,第 个班从第 小时开始、第 小时结束。每个班都必须安排,一间教室同一时刻只能有一个班;一个班结束的时刻,下一个班可以立刻使用这间教室。

最少需要几间教室?

输入格式

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

输出格式

一行一个整数:最少需要的教室数。

样例

输入
3
1 3
2 5
4 7
输出
2

样例解释

第一间教室安排 和 ( 时刻结束、 时刻开始,可衔接);第二间教室安排 。两间够用,一间不够(三个班中任意两个都有重叠时段)。

数据范围

,。

输入
输出

            
答案