logo AlgoBeat OnlineJudge
登录 注册

#200657. [USACO04DEC] Cleaning Shifts S

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

一天有 个时段。约翰正打算安排他的 只奶牛来值班,打扫打扫牛棚卫生。每只奶牛都有自己的空闲时间段 ,只能把空闲的奶牛安排出来值班。而且,每个时间段必须有奶牛在值班。

那么,最少需要动用多少奶牛参与值班呢?如果没有办法安排出合理的方案,就输出

输入格式

行:

行:

输出格式

一行,输出最少安排的奶牛数。

样例

样例输入 1

3 10
1 7
3 6
6 10

样例输出 1

2

数据范围与提示

:添加了一组hack数据,详情见这里。叉掉了时间复杂度为 的错解。