董事长度蜜月
1 Sec 32 MB |
148 | 294 |
通过 | 提交 |
题目描述
众所周知,男人有钱就会变坏,董事长也不例外。自从董事长担任这个职务以来,他就拥有了n个女朋友,当然了,每个女孩子都不知道彼此的存在。今年董事长决定要去度蜜月,每个女孩子都告诉了董事长一个度蜜月的开始日期和结束日期(由于太爱了,结束这一天也必须和一起度假的这个女朋友呆在一起)。因为董事长很爱她们,所以他想要尽可能多的和他的女朋友们度蜜月。又为了不让她们发现彼此的存在,所以他同时只能和一个女朋友度蜜月。由于女朋友们实在是有点多,董事长请你写个程序帮他计算一下,他今年最多能和几个女朋友去度蜜月呢?
输入格式
多组样例(不超过100组)。输入到文件结束。
第一行一个正整数n,代表女朋友们的数量(1<=n<=100)。
接下来n行,每行两个正整数a和b,以空格分开,表示这个女孩子要求的和董事长度蜜月的开始时间和结束时间(1<=a<=b<=10,000,000)。
输出格式
输出一个整数占一行,表示董事长最多能和多少个女朋友去度假。
样例输入 #1
1 1 2 2 1 3 2 4 2 1 3 3 4
样例输出 #1
1 1 1
提示
样例中的第三组,由于第一个女朋友结束日期和第二个女朋友的开始日期冲突了,所以只能在两个中选一个。
来源
Author gym