普及-⏱ 1000ms💾 256MB#P3012

题目描述

小镇要办节日演出,$n$ 个节目组报名,每个节目有一个开始时间 $s_i$ 和结束时间 $e_i$(同一时间只能演一个节目,前一个结束后一个才能开始,$e_i = s_{i+1}$ 允许)。

主办方想安排尽可能多的节目,输出最多能安排几个。

输入格式

第一行,一个整数 $n$

接下来 $n$ 行,每行两个整数 $s_i, e_i$,用空格分隔。

输出格式

一行,一个整数,表示最多能安排的节目数。

数据范围

$$1 \le n \le 10^5,\ 1 \le s_i < e_i \le 10^9$$

样例输入 #1
3
1 3
2 5
4 7
样例输出 #1
2
样例输入 #2
4
1 2
2 3
3 4
4 5
样例输出 #2
4