You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

C. 旅店的房间

题目描述

有 $n$ 位旅客将在未来几天内到达旅店入住。 已知各人在哪天入住，哪天退房。 请计算，要满足这些旅客的需求，至少要多少个房间。 两个旅客可以使用同一个房间，仅当“一人的退房日期小于另一人的入住日期”。

输入

第一行，整数 $n$。 下面 $n$ 行，每行两个整数 $a,b$，表示此人在日期 $a$ 开始时入住，日期 $b$ 结束后退房。

输出

一个整数，最少需要的房间数。

样例 1

输入

5
1 3
3 5
5 7
8 9
6 7

输出

2

解释 旅客1,3,4安排一个房间；旅客2,5安排一个房间。

数据范围

• 100%数据：$1 \le n \le 10^5; 1 \le a \le b \le 10^9$