Problem5892--主持人调度

5892: 主持人调度

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有 $n$ 个活动即将举办,每个活动都有活动的开始时间与活动的结束时间,第 $i$ 个活动的开始时间是 $start_i$,第 $i$ 个活动的结束时间是 $end_i$,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,活动主持人参与了第 $i$ 个活动,那么该主持人在 $start_i,\ end_i$ 这个时间段不能参与其他任何活动。
求为了成功举办这 $n$ 个活动,最少需要多少名主持人。

Input

第一行包括一个整数 $n\ (1 \leq n \leq 10^5)$。
其后 $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
需要两个主持人才能成功举办这两个活动。

Source/Category