问题 3809 --最大不相交区间数量

3809: 最大不相交区间数量

时间限制: 1 Sec  内存限制: 256 MB
提交: 32  解决: 28
[提交][状态][讨论版][命题人:]

题目描述

给定n个闭区间【ai,bi】,请你在数轴上选择若干区间，使得选中的区间互不相交（包括端点）。输出可选取区间的最大数量

输入

第一行包含一个正整数N,表示区间个数

接下来N行，每个整数a,b;表示一个区间的两个端点。

输出

输出一个整数，表示所选择的区间的最大数量

样例输入

3
-1 1
2 4
3 5

样例输出

2

提示


1<=N<=105



-109<=ai<=bi<=109

来源

贪心 

[提交][状态]