TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3769
  • 問題
  • P3769矩形覆盖
    制限 : 時間制限 : - MS   メモリ制限 : 65536 KB
    審判説明 : 1000ms
    問題説明

    数轴上有n个矩形排成一排,现在要求你用尽量少的矩形将它们恰好完全盖住,问,覆盖它们最少需要多个矩形。
         例如,图1的中的5个矩形至少需要如图2中的4个矩形才能将它们恰好盖住。

                            图1

                           图2

    入力形式

    第一行,一个整数n。
    接下来n行,每行两个整数x和y,从左往右依次给出了每个矩形的宽度和高度。

    出力形式

    一个整数表示所求答案

    サンプル入力 1

    5
    1 2
    1 3
    2 2
    2 5
    1 4

    サンプル出力 1

    4

    サンプル入力 2

    7
    2 3
    4 1
    1 2
    1 4
    2 4
    1 5
    4 4

    サンプル出力 2

    5

    ヒント

    对于30%的数据, 1<=n<=2000           

    对于100%的数据,1<=n<=250000          1<=x,y<=1000000000


    ソース  POI2008 PLA