#O1030. 活动安排
活动安排
题目描述
有 个活动,第 个活动占用时间段 。同一时刻只能进行一个活动,若一个活动在 结束、另一个在 开始,两者不冲突。问最多能参加多少个活动。
题目类型
贪心
输入格式
第一行一个整数 。
接下来 行,每行两个整数 。
输出格式
一行一个整数,表示最多能参加的活动数。
样例 #1
样例输入 #1
3
1 3
2 5
4 6
样例输出 #1
2
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 活动数 | |
| 时间范围 |
- 按结束时间升序贪心即可。
有 n 个活动,第 i 个活动占用时间段 [li,ri]。同一时刻只能进行一个活动,若一个活动在 r 结束、另一个在 r 开始,两者不冲突。问最多能参加多少个活动。
贪心
第一行一个整数 n。
接下来 n 行,每行两个整数 li,ri。
一行一个整数,表示最多能参加的活动数。
3
1 3
2 5
4 6
2
| 数据范围 | 说明 |
|---|---|
| 1≤n≤105 | 活动数 |
| 0≤li≤ri≤109 | 时间范围 |