算法:字母和信封配对

Question

免责声明:这不是任何一种功课,在我浏览所有圣诞卡时,我才想到这个问题

问题如下:我们有M个信封和N个字母,每个字母被描述为一对正整数.信封和字母都是矩形的,显然可以旋转.如果两个尺寸都小于或等于信封的尺寸,则字母会放入信封中.目标是找到最大的信封 - 字母匹配.

该问题很容易转换为最大的二分匹配问题,其中O(sqrt(M+N) * MN)存在一个运行的算法(Hopcroft-Karp,转换平常运行O(MN)).我试图提出一个贪婪的算法或动态的方法,但我没有找到任何.

你知道更快的解决方案吗？

Answer 1

以下“贪婪”型方法可能会有所帮助。

定义 m[i] 为包络 i 的两个整数中的最小值。

mins = distinct values of m[i], in increasing order
letters_to_match = all letters
for min in mins:
    envs = envelopes i with m[i] == min
    match letters_to_match with envs
    remove matched letters from letters_to_match