5892: 主持人调度
[Creator : ]
Description
有 $n$ 个活动即将举办,每个活动都有活动的开始时间与活动的结束时间,第 $i$ 个活动的开始时间是 $start_i$,第 $i$ 个活动的结束时间是 $end_i$,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,活动主持人参与了第 $i$ 个活动,那么该主持人在 $start_i,\ end_i$ 这个时间段不能参与其他任何活动。
求为了成功举办这 $n$ 个活动,最少需要多少名主持人。
求为了成功举办这 $n$ 个活动,最少需要多少名主持人。
Input
第一行包括一个整数 $n\ (1 \leq n \leq 10^5)$。
其后 $n$ 行,每行包括两个整数。第 $i$ 行表示活动 $i$ 的开始时间 $start_i$ 和结束时间 $end_i$,时间都在 int 范围之内。
其后 $n$ 行,每行包括两个整数。第 $i$ 行表示活动 $i$ 的开始时间 $start_i$ 和结束时间 $end_i$,时间都在 int 范围之内。
Output
一行一个整数,表示答案。
Sample 1 Input
2
1 2
2 3
Sample 1 Output
1
只需要一个主持人就能成功举办这两个活动。
Sample 2 Input
2
1 3
2 4
Sample 2 Output
2
需要两个主持人才能成功举办这两个活动。