最少教室数

题目描述

给定 n 个课程，每个课程有一个开始时间 s_i 和结束时间 e_i。同一时间不能在同一教室上两门课，问最少需要几个教室。

注意：如果一门课在时间 t 结束，另一门课在时间 t 开始，它们不算冲突，可以安排在同一教室。

输入格式

第一行一个整数 n (1 <= n <= 20)。 接下来 n 行，每行两个整数 s_i, e_i (0 <= s_i < e_i <= 10^9)，表示第 i 门课程的开始时间和结束时间。

输出格式

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

样例

输入：

3
0 30
5 10
15 20

输出：

2

数据范围

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

时间均为整数。