13065 - 活动选择

学校最近有 n 个活动，这些活动都需要使用学校的大礼堂。同一时间，礼堂只能被一个活动使用。由于部分活动在时间上存在冲突，学校办公室需要选择尽可能多的活动安排进礼堂，使得这些活动互不冲突（即任意两个活动的时间不能重叠，包括端点，通常结束时间 ≤ 下一个开始时间）。

给定每个活动的起始时间 begin 和结束时间 end（保证 begin < end），请你计算最多能安排多少个活动。

• 第一行包含一个整数 n （ 1 \le n \le 1000 ），表示活动的总数。
• 接下来 n 行，每行包含两个整数 begin 和 end，分别表示活动的开始和结束时间，满足 begin < end ≤ 32767。

输出一个整数，表示最多能安排的活动个数。

样例说明

一种可行的安排方案是选择活动：

• [1, 4]
• [5, 7]
• [8, 11]
• [12, 14]

共 4 个活动，且无法安排更多。

数据范围与约定

• 1 \le n \le 1000
• 0 \le begin < end \le 32767

一本通