Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2510
Concentric Rings

Time Limit: 2 Seconds      Memory Limit: 65536 KB

There are several different concentric rings on the ground. Some of them may overlap. In Figure 1, there are 3 rings: blue, green and red. The red one is just above the green one. The problem is to remove minimum number of rings so that no two of the remaining overlap.

Figure 1

The input consists of multiple test cases. Each test case starts with a positive integer N (<=10000) which represents the number of rings. The next N lines each line contains two positive integers which represents the inner radius and outer radius respectively.


For each test case, output the minimum number of rings to remove.

Sample Input:
1 2
3 6
4 5
Sample Output:

Author: XU, Chuan
Source: CYJJ's Funny Contest #1, Killing in Seconds
Submit    Status