TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3916
  • 問題
  • P3916刷题
    制限 : 時間制限 : - MS   メモリ制限 : 165536 KB
    審判説明 : 2s
    問題説明

    寒假里,何老板安排信竞班的N名学生去NKOJ刷题。
    寒假总共有T分钟,何老板要求每一分钟都至少有一个同学在刷题。这样的要求,让同学们很是恼火。
    每个学生只愿抽出一段特定时间刷题,比如第i个学生只愿意在[Si,Ei]这个时间段刷题。
    假期里大家都想玩,于是同学们想计算出最少需要安排多少个同学刷题就能满足要求。如果无解输出-1.

    入力形式

    第1行:两个整数N和T.

    接下来N行,每行两个整数表示一个学生刷题的时间段[Si,Ei]

    出力形式

     最少安排刷题的学生数.

    サンプル入力 1

    3 10
    1 7
    3 6
    6 10

    サンプル出力 1

    2

    サンプル入力 2

    3 10
    1 3
    4 7
    8 10

    サンプル出力 2

    3

    サンプル入力 3

    7 1000000
    1 100000
    99999 100001
    100000 200000
    200000 500000
    210000 490000
    499992 799987
    799988 1000000

    サンプル出力 3

    5

    ヒント

    1≤T≤1000000
    1≤N≤25000
    1≤Si≤Ei≤T
    样例1说明
    假期总共10分钟,安排学生1和学生3参与刷题即可保证每分钟都至少有一个同学在刷题.


    ソース  改编自Usaco2004 Dec Cleaning Shifts