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$。