U492913 区间分组

题目描述

学校最近开会特别频繁,会场安排负责人小A,整天忙于应付安排会场。 今天小A又收到全校的共 $n$ 个会议清单,其中第 $i$ 个会议在 $l_i$ 时开始,$r_i$ 时结束。 同一个会场不能同时进行两个不同的会议,如果一个会议结束时另一个会议刚好开始,这两个会议也不能在同一会场进行,因为中间没有时间准备。 请你计算:这 $n$ 个会议,至少需要安排多少个会场。

输入格式

第一行一个正整数 $n$ 表示会议个数。 接下来 $n$ 行每行两个自然数 $l_i, r_i$,表示第 $i$ 个会议的开始和结束的时间。

输出格式

输出一个整数,表示最少需要准备几个会场。假设学校会场足够多。

说明/提示

数据范围 - 对于 $40\%$ 的数据:$1\leq n\leq 10^3,0 \le l_i, r_i \le 10^3$; - 对于 $60\%$ 的数据:$1\leq n\leq 10^5,0 \le l_i, r_i \le 10^6$; - 对于 $100\%$ 的数据:$1\leq n\leq 10^5,0 \le l_i, r_i \le 10^9$。