24584-21 区间相交问题

2458   4-21 区间相交问题

题目描述

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

输入格式:

输入数据第一行是正整数n,表示闭区间数。接下来的n行中,每行有2 个整数,分别表示闭区间的2个数端点。

输出格式:

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

输入样例 复制
3
10 20
10 15
20 15
输出样例 复制
2

说明

1
1
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型
难        度