5800: 区间相交

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:75 Solved:3

Description

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

Input

第一行是正整数n,表示开区间数。接下来的n行中,每行有2 个整数,分别表示开区间的2个端点。(n<=100,端点坐标均小于1000)

Output

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

Sample Input Copy

3
10 20
10 15
15 20

Sample Output Copy

1

Source/Category