Why Did the Cow Cross the Road

题目描述

农夫约翰的奶牛们正在学习如何高效地过马路。 想起了那个经典的“为什么鸡要过马路？”笑话，她们认为鸡一定是过马路的专家，于是去寻找鸡来帮忙。

事实证明，鸡很忙，能帮助奶牛的时间很有限。农场里有 $C$ 只鸡（$1 \leq C \leq 20,000$），方便起见编号为 $1 \ldots C$，并且每只鸡 $i$ 只愿意在恰好时间 $T_i$ 帮助一头奶牛。奶牛们从不着急，时间安排更灵活。农场里有 $N$ 头奶牛（$1 \leq N \leq 20,000$），方便起见编号为 $1 \ldots N$，其中奶牛 $j$ 能在时间 $A_j$ 到时间 $B_j$ 之间过马路。奶牛们认为“结伴系统”是最好的方式，因此每头奶牛 $j$ 理想情况下都希望找到一只鸡 $i$ 来帮助她过马路；为了使双方时间安排兼容，$i$ 和 $j$ 必须满足 $A_j \leq T_i \leq B_j$。

如果每头奶牛最多只能与一只鸡配对，且每只鸡最多只能与一头奶牛配对，请帮助计算最多能构造出多少对奶牛-鸡配对。

输入格式

第一行输入包含 $C$ 和 $N$。接下来 $C$ 行包含 $T_1 \ldots T_C$，再接下来 $N$ 行包含 $A_j$ 和 $B_j$（$A_j \leq B_j$），其中 $j = 1 \ldots N$。$A$、$B$ 和 $T$ 都是非负整数（不一定互不相同），大小不超过 1,000,000,000。

输出格式

请计算最多可能的奶牛-鸡配对数量。

5 4
7
8
6
2
9
2 5
4 9
0 3
8 13

3

提示

题目来源：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver