区间相交问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

Input

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

Output

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

Sample Input

3
10 20
10 15
20 15

Sample Output

2

Hint

Source