飞题解

思路

把每个风口看作一个可分配的时间点，把每只猪看作一个可接受时间点的闭区间。问题是求时间点与区间之间的最大匹配。

将风口时间从小到大处理。处理时间 $p$ 时，所有满足 $s_i\le p$ 且尚未处理的猪都已经可以使用该风口。删除其中满足 $t_i<p$ 的猪，因为它们以后也不可能再匹配。若仍有候选，应把当前风口分配给结束时间最早的猪。

正确性证明

考虑当前最早的尚未处理风口 $p$。若没有清醒的猪可用，跳过它显然不会减少最优答案。否则设贪心选择的猪为 $a$，其结束时间最早。

任取一个最优方案。如果该方案没有使用风口 $p$，而猪 $a$ 在方案中使用了更晚的风口，则可把猪 $a$ 改到 $p$；如果猪 $a$ 未被使用，则直接让它使用 $p$，不会使答案变差。若该方案把 $p$ 分配给另一只猪 $b$，而猪 $a$ 使用了更晚的风口 $q$，由于 $t_a\le t_b$ 且 $q\le t_a$，猪 $b$ 也能使用 $q$，交换两只猪即可。若猪 $a$ 未使用，则用 $a$ 替换 $b$ 即可。

因此总存在一个最优方案与贪心在当前风口的选择一致。逐个风口重复上述交换，可知贪心得到最大匹配数。

做法

按开始时间排序所有猪，按时间排序所有风口。扫描风口时，将开始时间不晚于当前风口的猪的结束时间加入小根堆，先弹出已经结束的猪，再取堆顶完成一次匹配。

复杂度

排序与堆操作的总时间复杂度为 $O((n+m)\log m)$，空间复杂度为 $O(m)$。