奶牛日光浴问题

题目描述

有 $C$ 头奶牛进行日光浴，第 $i$ 头奶牛需要 $minSPF[i]$ 到 $maxSPF[i]$ 单位强度之间的阳光。

每头奶牛在日光浴前必须涂防晒霜，防晒霜有 $L$ 种，涂上第 $i$ 种之后，身体接收到的阳光强度就会稳定为 $SPF[i]$，第 $i$ 种防晒霜有 $cover[i]$ 瓶。

求最多可以满足多少头奶牛进行日光浴。

输入格式

第一行输入整数 $C$ 和 $L$。

接下来的 $C$ 行，按次序每行输入一头牛的 $minSPF$ 和 $maxSPF$ 值，即第 $i$ 行输入 $minSPF[i]$ 和 $maxSPF[i]$。

再接下来的 $L$ 行，按次序每行输入一种防晒霜的 $SPF$ 和 $cover$ 值，即第 $i$ 行输入 $SPF[i]$ 和 $cover[i]$。

每行的数据之间用空格隔开。

输出格式

输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

输入输出样例 #1

输入 #1

3 2
3 10
2 5
1 5
6 2
4 1

输出 #1

2

输入输出样例 #2

输入 #2

5 3
1 3
2 4
3 5
4 6
5 7
2 2
3 1
5 2

输出 #2

4

限制条件

• $1 \le C, L \le 2500$
• $1 \le minSPF \le maxSPF \le 1000$
• $1 \le SPF \le 1000$

样例解释 #1

有 $3$ 头奶牛：

1. 奶牛 1：需要阳光强度在 $[3, 10]$ 之间
2. 奶牛 2：需要阳光强度在 $[2, 5]$ 之间
3. 奶牛 3：需要阳光强度在 $[1, 5]$ 之间

有 $2$ 种防晒霜：

1. 防晒霜 1：$SPF = 6$，有 $2$ 瓶
2. 防晒霜 2：$SPF = 4$，有 $1$ 瓶

最优分配方案：

• 奶牛 1 使用防晒霜 1（$6 \in [3, 10]$）
• 奶牛 3 使用防晒霜 2（$4 \in [1, 5]$）
• 奶牛 2 无法使用任何防晒霜（没有 $SPF \in [2, 5]$ 的防晒霜了）

最多可以满足 $2$ 头奶牛。

解题思路

这是一个典型的贪心匹配问题：

1. 将所有奶牛按照 $minSPF$ 从大到小排序
2. 将所有防晒霜按照 $SPF$ 从大到小排序
3. 对于每头奶牛（按排序后的顺序），选择 $SPF$ 最大且不超过该奶牛 $maxSPF$ 的防晒霜
4. 如果找到合适的防晒霜且该防晒霜还有剩余，则分配给这头奶牛，计数加一

这样贪心的正确性在于：对于 $minSPF$ 较大的奶牛，它们的选择范围较小，应该优先考虑；而对于 $SPF$ 较大的防晒霜，它们适用的奶牛范围也较小，应该优先使用。