题目描述

有 $n$ 部电影要放映，第 $i$ 部电影放映的时间是 $l_i$ 到 $r_i$，区间重叠的电影不可能同时看（端点可以重合），问最多可以看多少部电影。

输入格式

第一行是 $n(1 \le n \le 100)$，表示共 $n$ 场电影。

接下来 $n$ 行，每行两个整数 $l, r(0 \le l, r \le 1000)$，表示一场电影的放映区间

输出格式

对每组数据输出最多能看几部电影

8
3 4
0 7 
3 8 
15 19
15 20
10 15
8 18 
6 12

3

提示

【样例解释】

• 坐标系画图神奇: geogebra
• 可以观看 [3, 4], [6, 12], [15, 19] 3 场电影
• 思考下下面 3 种贪心策略，哪个是正确的
• 1）依次选择 最早开始 的电影
• 2）依次选择 最早结束 的电影
• 3）依次选择 耗时最短 的电影
• 4）依次选择 与其他电影重叠最少 的电影

数据规模与限制

• $1 \le n \le 100, 0 \le l,r \le 1000$

来源