#O1030. 活动安排

活动安排

题目描述

有 nn 个活动,第 ii 个活动占用时间段 [li,ri][l_i, r_i]。同一时刻只能进行一个活动,若一个活动在 rr 结束、另一个在 rr 开始,两者不冲突。问最多能参加多少个活动。

题目类型

贪心

输入格式

第一行一个整数 nn。

接下来 nn 行,每行两个整数 li,ril_i, r_i。

输出格式

一行一个整数,表示最多能参加的活动数。

样例 #1

样例输入 #1

3
1 3
2 5
4 6

样例输出 #1

2

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 活动数
0≤li≤ri≤1090 \le l_i \le r_i \le 10^9 时间范围
  • 按结束时间升序贪心即可。