#S5U12P03. 【例题】最多参加几场

【例题】最多参加几场

最多参加几场

难度:T2

【知识点:贪心】【知识点:交换论证】

前置知识:循环、排序、数组或结构体。

题目描述

给n场活动的开始s和结束e,完整参加后才算一场。不能同时参加时间重叠的活动。活动占用左闭右开区间,上一场结束与下一场开始相等时允许衔接。求最多能参加多少场。

输入格式

第一行n,随后n行各给开始s、结束e。

输出格式

一行一个整数,表示题目要求的最优数量。

样例输入

4
1 2
0 3
2 4
4 5

样例输出

3

样例说明

参加1到2、2到4、4到5三场可衔接。

数据范围

1≤n≤20001\le n\le2000,0≤s<e≤1060\le s<e\le10^6。