最大化阵列之间的最小距离

Question

假设您有 n 个排序的数字数组，您需要从每个数组中选择一个数字，以使 n 个所选元素之间的最小距离最大化。

例子：

arrays:
[0, 500]
[100, 350]
[200]

2<=n<=10每个数组都可以有~10^3-10^4元素。

在此示例中，最大化最小距离的最佳解决方案是选择数字：500、350、200 或 0、200、350，其中最小距离为 150，并且是每个组合的最大可能值。

我正在寻找一种算法来解决这个问题。我知道我可以对最大最小距离进行二分搜索，但我不知道如何确定是否存在最大最小距离至少为 d 的解决方案，以便二分搜索起作用。我在想动态编程可能会有所帮助，但还没有找到 dp 的解决方案。

当然，用 n 个元素生成所有组合效率不高。我已经尝试过回溯，但速度很慢，因为它尝试了每种组合。

Answer 1

我将给出一个算法，对于给定的距离d，将输出是否可以做出选择，其中任何一对选定数字之间的距离至少为d。然后，您可以对算法输出“YES”的最大值进行二分搜索d，以找到问题的答案。

d假设给定最小距离。这是算法：

for every permutation p of size n do:
    last := -infinity
    ok := true
    
    for p_i in p do:
        x := take the smallest element greater than or equal to last+d in the p_i^th array (can be done efficiently with binary search).
        if no such x was found; then
            ok = false
            break
        end

        last = x
    done

    if ok; then
        return "YES"
    end
done

return "NO"

因此，我们对数组的顺序进行暴力破解。然后，对于每个可能的顺序，我们使用贪婪方法按照顺序从每个数组中选择元素。例如，以您给出的例子为例：

arrays:
[0, 500]
[100, 350]
[200]

并假设d = 150. 对于排列1 3 2，我们首先从第一个数组中取出 0，然后在第三个数组中找到大于或等于 0+150（即 200）的最小元素，然后在第二个数组中找到最小的元素大于或等于200+150（即350）。由于我们可以从每个数组中找到一个元素，因此算法输出“YES”。但对于d = 200例如，该算法将输出“NO”，因为所有可能的排序都不会导致成功的选择。

上述算法的复杂度是O(n! * n * log(m))其中m是数组中元素的最大数量。我相信这已经足够了，因为n它很小。（对于m = 10^4, 10! * 10 * 13 ~ 5*10^8。它可以在现代 CPU 上在一秒内完成计算。）