2392. 活动选择问题
1000ms
256MB
简单
贪心算法
排序
模拟法
题目描述
现有 $n$ 个活动，每个活动都有已知的开始时间点和结束时间点。
在同一时间只能参加一个活动，且参加活动必须全程参与（即一个活动的开始时间必须大于或等于上一个活动的结束时间）。
请计算并输出最多能够参加的活动数量。
输入格式
- 第一行包含一个正整数 $n$ ($1 \le n \le 10^6$)，表示活动的个数。
- 接下来 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($0 \le a_i < b_i \le 10^6$)，分别表示第 $i$ 个活动的开始时间和结束时间。
输出格式
- 输出一个整数，表示最多能参加的活动数量。
样例 1
输入 (Input)
3 0 2 2 4 1 3
输出 (Output)
2
样例说明
可以参加活动 1（时间为 $[0, 2]$）和活动 2（时间为 $[2, 4]$），总活动数为 2。活动 3（时间为 $[1, 3]$）与活动 1、活动 2 均有时间冲突，无法参加。
- 对于 $20\%$ 的数据：$n \le 10$。
- 对于 $50\%$ 的数据：$n \le 10^3$。
- 对于 $70\%$ 的数据：$n \le 10^5$。
- 对于 $100\%$ 的数据：$1 \le n \le 10^6$，$0 \le a_i < b_i \le 10^6$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功