主持人调度(二)
题号:NC216554
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有 n 个活动即将举办,每个活动都有开始时间与活动的结束时间,第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动,换句话说,一个主持人参与了第 i 个活动,那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动,最少需要多少名主持人。

数据范围: -2^{32} \le start_i\le end_i \le 2^{31}-1

复杂度要求:时间复杂度 ,空间复杂度
示例1

输入

复制
2,[[1,2],[2,3]]

返回值

复制
1

说明

只需要一个主持人就能成功举办这两个活动      
示例2

输入

复制
2,[[1,3],[2,4]]

返回值

复制
2

说明

需要两个主持人才能成功举办这两个活动      

备注:

start_i,end_i在int范围内