Problem F
Air Conditioned Minions

You are the boss of ACM (Air Conditioned Minions), an upstanding company with a single goal of world domination.

The company has $N$ minions. Each minion works evilly from early morning until evening inside a super secret bunker in Helsinki. After much deliberation, you decided to move your headquarters to Singapore. However, unlike Helsinki, Singapore is very hot, so the entire complex must be air conditioned. With strenuous working hours (under minimum wage too), it is imperative that all your minions work under optimal work condition. In particular, all minions must like the temperatures of the rooms they are in.

You are planning to construct several rooms in your new hideout, and assign your minions there. You fix the temperature of each room to any value you want (different rooms may have different temperatures). After you fix the temperatures, you will assign each of your minions to these rooms (a room can hold any number of minions). You want all minions to like the temperatures of their assigned rooms. Each minion likes an interval of temperature, and these preferences will be given to you.

Air conditioners are very expensive to maintain. Thus, you want to construct as few rooms as possible. What is the minimum number of rooms you need to set up such that it would be possible to assign minions to rooms as discussed earlier?


The first line contains a non-negative integer $2 \leq N \leq 100$, giving the number of minions in your company. The next $N$ lines each describe the temperature preferences of all your minions. The $i$-th line consists of two single space separated integers $L$ and $U$ ($1 \le L \le U \le 2N$), which denotes that the $i$-th minion likes any temperature between $L$ and $U$, inclusively.


Print an integer denoting the minimum number of rooms you need to construct.

Sample Data Explanation

In the first example, one of the possible solutions is to setup two rooms — one with temperature $2$, and another with temperature $5$. The first two minions can be assigned to the first room, while the third minion can be assigned to the second room.

Sample Input 1 Sample Output 1
1 2
2 4
5 6
Sample Input 2 Sample Output 2
1 2
3 5
4 6
7 9
8 10

Please log in to submit a solution to this problem

Log in