多教室活动分配（经典扩展）

题目描述

有 n 个活动，每个活动有一个开始时间 s_i 和结束时间 e_i。一个教室同一时间只能进行一个活动。问最少需要多少个教室才能安排所有活动。

注意：如果一个活动在时间 t 结束，另一个活动在时间 t 开始，它们可以共用同一个教室。即区间视为左闭右开 [s_i, e_i)。

输入格式

第一行一个整数 n (1 <= n <= 100)。 接下来 n 行，每行两个整数 s_i, e_i (0 <= s_i < e_i <= 10^9)。

输出格式

一个整数，表示最少需要的教室数。

样例

输入：

3
1 3
2 4
3 5

输出：

2

解释：活动 1 和活动 3 可以共用教室，活动 2 需要另一个教室。

数据范围

1 <= n <= 100 0 <= s_i < e_i <= 10^9