提示: 欢迎访问OurACM平台。
Problem 1230 区间相交问题

Accept: 715    Submit: 2173
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

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

★算法设计: 对于给定的 n 个闭区间,计算去掉的最少闭区间数。

Input

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

Output

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

Sample Input

3 10 20 15 10 20 15

Sample Output

2

Source

FJ CFCS 2008

Submit  Back  Status  Discuss