题目描述
社团 tonight 有 场活动,第 场从时刻 开始、 结束()。一个人同一时刻只能参加一场,且参加一场活动必须从头到尾在场——上一场结束的时刻恰好等于下一场开始的时刻是可以衔接的。
请计算最多能完整参加多少场活动。
输入格式
第一行一个整数 。
接下来 行,每行两个整数 。
输出格式
一个整数:最多能完整参加的活动场数。
样例
输入:
5
1 4
2 3
3 5
4 6
5 7
输出:
3
(参加 (2,3)、(1,4)、(5,7) 三场。)
提示
先按结束时间从小到大排序,能参加就参加——这就是经典的「最早结束优先」贪心。
数据范围
;。
说明
- 本题为本站自拟/改编题,已按题目要求生成完整测试数据。