提示: 欢迎访问OurACM平台。
Problem 1574 一食堂宣传栏

Accept: 247    Submit: 559
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在福州大学,一区食堂“桃李园”外的宣传栏是一个竞争很激烈的资源,每天总有大量的海报张贴,后贴的往往会盖住原先的,为此很多学生抱怨。学校有关部门下决心解决这个问题,他们要求海报在张贴的前一天登记,然后他们根据各海报申请的位置确定第二天要贴哪些海报。选择的标准就是:海报的数量尽可能多,且不能相互重叠。学校相关部门委托你编程选择最优的方案。

为了简化问题我们规定:

  1. 宣传栏用一个区间[-9999,9999]来表示;
  2. 海报的高度均与宣传栏的高度相同,各海报要登记两个整数left,right(right>left),表示传单要占据区间[left,right]
  3. 其中左右边框left和right没有文字,所以可以重叠;

要求海报张贴的数量尽可能多,以最大程度满足需求。

Input

输入包括多组数据,每组输入的第一行是一个整数n(n<1000),表示要张贴的海报张数。
下面有n行,每行两个整数 left, right (不一定按大小顺序排列,-9999<left<9999,-9999<right<9999),表示每张海报的申请张贴的位置。

Output

对于每组数据,输出为一个整数,表示要张贴的海报数。

Sample Input

3 6 4 1 4 3 5 2 8469 -3664 -3494 9171

Sample Output

2 1

Source

FOJ月赛-2008年3月

Submit  Back  Status  Discuss