题目描述

有 $n$ 名同学申请使用自修教室，其中第 $i$ 名同学申请从第 $s_i$ 天开始使用，到第 $t_i$ 天结束时归还。每间自修教室在同一天只能供一名同学使用，则为了满足所有同学的申请，至少需要多少间教室？

输入格式

• 第一行：单个整数 $n$；
• 第二行到第 $n+1$ 行：第 $i+1$ 行有两个整数 $s_i$ 与 $t_i$，表示一名同学申请教室的时间。

输出格式

• 单个整数：表示至少需要多少间教室才能满足所有学生的申请。

3
1 3
3 5
2 4

3

样例解释 1

三人各需要一间教室

3
1 10
20 30
40 50

1

数据范围

• 对于 $40\%$ 的数据，$1\leq n\leq 15$；
• 对于 $70\%$ 的数据，$1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100,000$；
• $1\leq s_i\leq t_i\leq 1,000,000$。