什么是选择 n 对以使对中的最大 Δ 尽可能小的贪婪算法？

Question

我有 n 只大小不一的小狗和 n 只大小不一的小猫，我想制作一对小狗和小猫。特别是，我想要一对尺寸差异尽可能小的小狗和小猫。

什么是一种高效的贪婪算法，它选择 n 对小狗-小猫，使得它们之间的大小差异 大多数大小不同的对越小越好？更准确地说，s_i 表示小狗 i 的大小，s_j 表示小猫 j 的大小。给定一对 ，令 ∆(i, j) = | s_i − s_j |。该算法应选择配对以确保所有配对中最大的 Δ(i, j) 尽可能小。

举个例子：有 6、4、9 号的三只小狗和 8、7、3 号的三只小猫。如果将它们配对 <6, 8>, <4, 7> , < 9, 3> 那么最大 Δ 就是 6，而如果你将它们配对 <6, 7> , <4, 3> , <9, 8> ，最大 Δ 就是 1，这显然是最优的（因为，例如， 6号的小狗只能 匹配一只小猫，其大小与小狗的大小相差 ≥ 1）。

Answer 1

一个最优贪心算法是：

1. 将小狗 从小到大排序（任意打破并列）。表示这样的列表 P.
2. 将小猫 从小到大排序（任意打破并列）。表示这样的列表 K.
3. Select 对 根据它们的索引 (P[0], K[0]), (P[1], K[1]), ..., (P[n - 1], K[n - 1]).

使用 交换论证。

可以 证明这种选择是最优的

定义: 如果有两对 (a, d) 和 (b, c) 这样 a < b 和 c < d.

引理 1：所有没有反转的排列都具有相同的 Δ。 （给你的任务 :P，比较 a = b 和 c < d、a < b 和 c = d 的情况）

声明：存在一个没有倒置的最优排列。
证明。至少存在一个最优排列，姑且称之为O.
如果 O 没有反转，我们就完成了。
否则在将 (a, d) 和 (b, c) 交换为 (a, c) 和 (b, d) 之后，我们得到了一个少了一次反转的最优排列。初始排列最多可以有 Cⁿ₂ 次反转，因此最多经过 Cⁿ₂ 交换我们得到一个没有倒置的最优排列。

我们知道 a < b 和 c < d。强制其他不等式：

1. a <= c 和 b <= d:
   |a - d| = max(|a - d|, |b - c|) >= max(|a - c|, |b - d|)
2. c <= a 和 b <= d:
   |a - d| >= |b - d| 和 |b - c| >= |a - c| 然后 max(|a - d|, |b - c|) >= max(|a - c|, |b - d|)
3. a <= c 和 d <= b:
   |a - d| >= |a - c| 和 |b - c| >= |b - d| 然后 max(|a - d|, |b - c|) >= max(|a - c|, |b - d|)
4. a >= c 和 d <= b:
   |b - c| = max(|a - d|, |b - c|) >= max(|a - c|, |b - d|)

在所有情况下，交换排列都不会增加 Δ 值，并且我们知道初始排列具有最佳 Δ 值，因此我们的说法是正确的。

通过引理1和声称贪心算法是最优的。