题目描述

学校的小礼堂每天都会有许多活动，有些活动的时间会冲突，因此需要选择一些活动进行安排。现在有 n 个活动，每个活动都有一个开始时间和结束时间。要求选出尽可能多的活动，使得它们之间互不冲突（即任意两个活动的时间区间不重叠）。

输入格式

第一行一个整数 n，表示活动数量。 接下来 n 行，每行两个整数 s 和 e，分别表示活动的开始时间和结束时间。

输出格式

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

样例输入1

4
1 3
2 5
3 6
5 7

样例输出1

2

样例解释1

选择活动 1（1-3）和活动 4（5-7），可以安排 2 个活动，这是最优解。

样例输入2

6
1 4
3 5
0 6
5 7
3 9
5 9

样例输出2

3

样例解释2

选择活动 1（1-4）、活动 4（5-7），以及不与其他活动冲突的活动，最多可安排 3 个活动。

数据范围

• 对于 30% 的数据，1 ≤ n ≤ 10
• 对于 60% 的数据，1 ≤ n ≤ 1000
• 对于 100% 的数据，1 ≤ n ≤ 10^5，0 ≤ s < e ≤ 10^9

提示

这是一道经典的贪心问题。贪心策略：按照结束时间从小到大排序，每次选择结束时间最早且与已选活动不冲突的活动。

证明：选择结束时间最早的活动可以为后面的活动留出更多时间，从而可能安排更多的活动。