算法:信件和信封配对

Question

免责声明:这不是任何形式的家庭作业，当我浏览所有的圣诞卡时，这个问题突然出现在我的脑海中。

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

这个问题很容易转换为最大二部匹配问题，对于这个问题，存在一个在O(sqrt(M+N) * MN)中运行的算法(Hopcroft-Karp，转换在O(MN)中运行得很简单)。我试图想出一种贪婪的算法或一种动态的方法，但我没有找到任何方法。

你知道有没有更快的解决方案？

Answer 1

下面的“贪婪”-type方法可能会有所帮助。

定义mi为包络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

Answer 2

这不是等同于最大二部匹配吗？

也就是说，假设你有一个解决这个问题的算法，那么你可以解决最大二部匹配。

给定一个二部图，我们可以将信封和字母(即两个正整数)分配给每个节点...

Answer 3

这是可以用2D垂直扫描线算法在O(max(M,N) log(max(M,N))) (对信件和信封进行排序的时间)中解决的。这与O(M+N log (M+N))相同。

由于允许旋转，因此可以交换任意一对字母/信封尺寸的

1. ，以便x <= y.

1. 合并列表，标记每个点的原始列表。例如，我们可以通过让(x, y, 'E')代表信封列表中的点，并让'L‘代表字母来实现这一点。

1. 按x对列表进行排序，然后按y对抢七进行排序，如果仍是平局，则在“E”之前加上“L”。我们将字母(x0, y0, 'L')视为2D空间中的一个点，当且仅当x0 <= y0 and x1 <= y1.

时，它才能匹配任何“包络”点(x1, y1, 'E')

1. 初始化平衡的二进制搜索树( BST ) unmatched_letters，它将包含迄今为止未匹配的字母，以及它们在BST中的关键字/仅基于其y值的排序。

我们的想法是，我们将在这些点上从左到右移动一条垂直扫描线，从下到上处理线上的点(这正是我们的列表已经排序的顺序)：

• 如果我们看到一个字母，我们会将它添加到我们的unmatched_letters BST中，按'y‘排序。这意味着我们在添加后看到的任何信封只需要检查更大/相等的'y‘值(扫描线确保后面的x值不小于)。
• 如果我们看到一个信封，我们将使用二进制搜索将它与BST中可用的最高高度的字母进行匹配。如果没有，我们可以“丢弃”/忽略那个信封，因为我们将来看到的任何字母都将具有比这个信封更高的x或y值。否则，匹配它们。你可以通过贪婪的交换论证表明这将给出最优解；如果它不是太长或不是微不足道的，我可能会包括这一点的证明。

有关我们刚才描述的步骤的更详细的“伪代码”版本：

1. 遍历列表中的(x0, y0, category)点。如果为category == 'L'，则使用密钥y0将其插入到unmatched_letters中。如果为category == 'E'，则对unmatched_letters中最大键值进行二进制搜索，最大键值为y0。如果有匹配:字母最多有一个x0的x值，因为它是在早些时候处理过的。删除该信件，并使用此信封将其记录为我们解决方案的一部分。

由于我们所做的只是对列表进行排序和迭代，这显然可以在O(sorting)中完成。不难解释为什么这必须提供最大匹配，但贪婪算法的正确性的确切证据可能很长。争论的一部分是这样的:如果我们与任何固定的、最优的解决方案进行比较，最早的差异(通过x坐标)是贪婪匹配信封'E1‘和字母'L1’，而最优不匹配，那么有两种可能性(不是不相交的)：

• 在最佳解决方案中，'E1‘与不同的字母'L2’相匹配。通过构造，'L2‘的y值最多与'L1’一样大，因此如果'L1‘与最优解中较晚的(通过x值)包络匹配，则后面的包络也必须与'L2’匹配(如果不匹配，我们可以在最优中交换'L1‘和'L2’以匹配贪婪)。
• 在最优解中，'L1‘与不同的包络'E2’匹配。然后，再一次，最优解中的信封'E1‘与一个小于或等于y值的字母(或空)相匹配，我们可以在最优解中交换这些配对，以匹配贪婪。