1575: 线段

题目描述


数轴上有n条线段，选取其中k条线段使得这k条线段两两没有重合部分，问k最大为多少。

输入


第一行为一个正整数n；
在接下来的n行中，每行有2个数 ai
,bi
，描述每条线段。

输出


输出一个整数，为k的最大值。

样例输入


3
0 2
2 4 
1 3

样例输出


2

提示


对于 20% 的数据，n≤10；
对于 50% 的数据，n≤103；
对于 70% 的数据，n≤105；
对于 100% 的数据，n≤106, 0≤ai
≤106。

来源/分类


ybttg 贪心

请先 登录 后评论
默认排序 时间排序

0 个回答

  • 0 关注
  • 0 收藏，385 浏览
  • 轩爸 提出于 2019-08-02 22:13

相似问题