问题 G: 自修教室
传统题
1.000s
时间限制
256MB
内存限制
3 提交
2 解决
【题目描述】
题目描述
有 n
名同学申请使用自修教室，其中第 i 名同学申请从第 si
分钟开始使用，到第 ti
分钟结束时归还。若每间自修教室在同一时刻只能供一名同学使用，则为了满足所有同学的申请，至少需要多少间教室？
输入格式
第一行：单个正整数 n；
第二行到第 n+1
行：第 i+1
行有两个正整数 si
与 ti
，表示一名同学申请教室的时间。
输出格式
单个正整数：表示至少需要多少间教室才能满足所有学生的申请。
数据范围
对于 40% 的数据，1≤n≤15
；
对于 70% 的数据，1≤n≤5000
；
对于 100% 的数据，1≤n≤100,000
；
1≤si≤ti≤1,000,000
。
样例数据
输入:
3
1 3
3 5
2 4
输出:
3
说明:
三人各需要一间教室
输入:
3
1 10
20 30
40 50
输出:
1