问题 3724 --闭区间问题

3724: 闭区间问题

题目描述

  给定 x 轴上 n 个闭区间。去掉尽可能少的闭区间,使剩下的闭区间都不相交。
对于给定的 n 个闭区间,计算去掉的最少闭区间数。

输入

对于每组输入数据,输入数据的第一行是正整数 n (1<=n<=40,000),表示闭区间数。接下来的 n 行中,每行有 2 个整数,分别表示闭区间的 2 个端点。

输出

输出计算出的去掉的最少闭区间个数。

样例输入输出

输入#1 复制
3
10 20
15 10
20 15
输出#1 复制
2

提示

序号 标题 作者 发表时间 费用 订购数 操作