‹ 上一题 下一题 ›

g4-06912. 活动安排 未做

1000 ms 256 MB 测试点 10 自拟题GESP-44级·结构体与多键排序排序应用

题目描述

社团 tonight 有 场活动,第 场从时刻 开始、 结束()。一个人同一时刻只能参加一场,且参加一场活动必须从头到尾在场——上一场结束的时刻恰好等于下一场开始的时刻是可以衔接的。

请计算最多能完整参加多少场活动。

输入格式

第一行一个整数 。

接下来 行,每行两个整数 。

输出格式

一个整数:最多能完整参加的活动场数。

样例

输入:

5
1 4
2 3
3 5
4 6
5 7

输出:

3

(参加 (2,3)、(1,4)、(5,7) 三场。)

提示

先按结束时间从小到大排序,能参加就参加——这就是经典的「最早结束优先」贪心。

数据范围

;。

说明

  • 本题为本站自拟/改编题,已按题目要求生成完整测试数据。
输入
输出

            
答案