TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • 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