python - 与最近邻居的最大差异

Question

我正在编写一个座位分配程序，并将问题集中在单排座位上。我想分配下一个座位，使其与最近的座位距离最远。我决定问题可以这样写:

给定一个整数列表(所有座位)和一个子集(已占座位)，找到与最近的相邻数字具有最大差异的最小整数。

例如:

Input: [1,2,3,4,5,6,7,8,9,10], [1,10]
Output: 5
(Actually it is 5 or 6 but we take the smallest)
Input: [1,2,3,4,5,6,7,8,9,10], [5,10]
Output: 1
(1 is 4 numbers away from 5, any other number is 3 or less numbers away from 5 or 10)
Input: [1,2,3,4,5,6,7,8,9,10], [1,5,10]
Output: 3
(Possible candidates are 3, 7 or 8 but we take the smallest)

我试图通过所取的子集循环每个剩余的整数并取平均值和差异之和，但输出不正确。

我确信已经有解决这个问题的算法。你会使用哪种算法(这样我就可以为自己设定正确的方向)？谢谢。

Answer 1

假设我们有从 1 到 n 的座位。请注意，答案是 1、n 或最大未采用子序列的中心。检查 1 和 n 的最近邻居很简单，所以让我们专注于寻找未采用的子序列。我认为在这种情况下，代码最适合自己:

largest_free = 0, largest_begin
current_free = 0, current_begin = 0
for i = 1 to n:
    if i is taken:
        if current_free > largest_free:
            largest_free = current_free
            largest_begin = current_begin
        current_begin = i + 1
        current_free = 0
    else:
        current_free += 1

if current_free > largest_free:
    largest_free = current_free
    largest_begin = current_begin

整个算法显然会花费线性时间。