1321: 区间相交

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Normal Judger Creator:
Submit:25 Solved:6

Description

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

给定 n 个闭区间,编程计算去掉的最少闭区间数。

Input

第一行是正整数 n,表示闭区间数。接下来的 n 行中,

每行有 2 个整数,分别表示闭区间的 2 个端点。 

Output

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

Sample Input Copy

3
10 20
10 15
20 15

Sample Output Copy

2

Source/Category