Responsive image

问题 2839 --清洁班次

2839: 清洁班次

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 42
[提交][状态][讨论版][命题人:]

题目描述

农夫想让奶牛去打扫仓库，打扫仓库的时间段为1~T，一共有n头牛，每个牛都有自己能工作的时间段（开始时间~结束时间），要求时间段1~T内每个时间点必须至少有一头牛在打扫仓库，问最少需要安排几头牛，若不能分配牛到每一个时间段，则输出-1。

输入描述

第 1 行：两个空格分隔的整数：N 和 T （1<=N<=25,000,1<=T<=1,000,000）
第 2..N+1 行：每行包含奶牛可以工作的间隔的开始和结束时间。一头奶牛在开始时间开始工作，在结束时间之后结束。

输出描述

第 1 行：输出农夫需要雇用的奶牛的最小数量，如果无法为整个打扫时间段分配奶牛则输出-1。

样例输入

3 10
1 7
3 6
6 10

样例输出

2

来源

21计1朱天宇 

[提交][状态]
ACM算法攻关部