#P2011. 选择不相交区间

选择不相交区间

  好吧。这道题的目的在于让大家认识贪心问题的三个区间经典问题:区间选点问题,区间覆盖问题,以及该题的选择不相交区间问题。有许多的贪心问题可以转化为这三类的问题。

  那么,对于该问题。就是给一系列的区间,求最多的区间,要求区间个数最多,这些区间不相交,需要注意的是这些区间都是闭区间。

Just For Fun

Input

第一行一个数n为区间个数(n<=1000)
接下来有n行,每行有两个数a,b分别为区间的两个端点,a,b在int范围。
EOF结尾。

Output

输出如样例所示

Sample Input

2
1 10
10 11
3
1 10
10 11
11 20

Sample Output

Case 1:
1.
Case 2:
2.

HINT

注意,A完这道题,如果你对上面的三个问题还没有太理解,请去学会。

Source