问题 3807 --区间分组（数据加强）

3807: 区间分组（数据加强）

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

题目描述

给定N个闭区间[ai,bi],请你将这些区分成若干组，使得每组内部区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输入

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

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

输出

输出一个组数，表示最小组数

样例输入

3
-1 1
2 4
3 5

样例输出

2

提示


1<=N<=105



-109<=ai<=bi<=109

来源

贪心 

[提交][状态]