普及⏱ 1000ms💾 256MB#P5133🏷️ 排序贪心

题目描述

创客空间有一台公用 3D 打印机,同学们提交了 $n$ 个打印申请, 第 $i$ 个申请要从时刻 $b_i$ 开始、时刻 $e_i$ 结束($b_i < e_i$,结束与下一次开始重合是允许的)。 打印机同一时刻只能执行一个申请,不相容的申请只能被婉拒。

请安排尽量多的申请使用打印机,输出最多能安排的申请个数。

输入格式

第一行一个整数 $n$; 接下来 $n$ 行,每行两个整数 $b_i, e_i$,表示一个申请的起止时刻。

输出格式

一行,一个整数:最多能安排的申请个数。

数据范围

$$1 \le n \le 1000,\quad 0 \le b_i < e_i \le 32767$$

样例输入 #1
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13
样例输出 #1
4
样例输入 #2
1
0 5
样例输出 #2
1