Максимальная разница от ближайшего соседа

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 

Общий алгоритм, очевидно, взять линейное время.

Answer 2

Следующий код о читаемости, необязательно из о производительности:

def find_max_dist(n, taken): 
    # trivial cases: no or one seat taken 
    if not taken: 
     return 1 
    elif len(taken) == 1: 
     return 1 if list(taken)[0] > n//2 else n 
    else: # interesting case 
     taken = sorted(list(taken)) 
     gap_sizes = list(map(lambda x,y: y-x-1, taken, taken[1:])) 
     biggest_gap_size = max(gap_sizes) 

     # check if outermost seats are optimal 
     if taken[0] > biggest_gap_size: 
      return 1 
     elif n - taken[-1] > biggest_gap_size: 
      return n 

     begin_of_biggest_gap = taken[gap_sizes.index(biggest_gap_size)] + 1 
     return begin_of_biggest_gap + ((biggest_gap_size - 1)// 2) 



print(find_max_dist(10, {})) 

print(find_max_dist(10, {5})) 
print(find_max_dist(10, {6})) 

print(find_max_dist(11, {5})) 
print(find_max_dist(11, {6})) 

print(find_max_dist(10, {1, 10})) 
print(find_max_dist(10, {5, 10})) 
print(find_max_dist(10, {1, 5, 10})) 

Я предполагаю, что taken представляет собой набор. Если этот набор пуст или содержит ровно один элемент, выбор ясен: первое место, если пустое или занятое место находится во второй половине, в последнем месте.

Если есть несколько занятых мест, определяется самый большой зазор. Затем код определяет, насколько оптимальным является первое, последнее или среднее седло в зазоре.

Для вашего последнего теста, должен быть ответом, потому что второй зазор больше.

Answer 3

Это кажется довольно оптимальным и читаемым мне:

try: 
    from itertools import izip 
except ImportError: # Python 3 
    izip = zip 
from operator import itemgetter 

def pairwise(iterable): 
    "s -> (s0, s1), (s1, s2), (s2, s3), ..." 
    return izip(*[iter(iterable)]*2) 

def find_max_dist(all_seats, taken_seats): 
    if len(taken_seats) == len(all_seats): # no empty seats? 
     return None 

    # adds a virtual seat 0 if left-most taken seat isn't 1 
    taken_seats = sorted(taken_seats + ([0] if taken_seats[0] != 1 else [])) 
    gaps = ((p0+1, p1-1, (p1-1)-(p0+1)) for p0, p1 in pairwise(taken_seats)) 
    max_gap = max(gaps, key=itemgetter(2)) # interval with largest gap 

    # if left-most seat of largest gap is seat 1, use it, else use gap midpoint 
    return 1 if max_gap[0] == 1 else (max_gap[0] + max_gap[1]) // 2 

seats = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

print(find_max_dist(seats, [1, 10])) # --> 5 
print(find_max_dist(seats, [5, 10])) # --> 1 
print(find_max_dist(seats, [1, 5, 10])) # --> 3 

Answer 4

Спасибо за ответы на все вопросы и отзывы. Принимая во внимание все это, это мое окончательное решение.

def findnextseat(n,taken): 
    longestgapstart = 0 
    longestgaplength = 0 
    gapstart = 0 
    gaplength = 0 
    for i in range(1,n+1): 
     if len(taken) == 0: 
      longestgapstart = 1 
      longestgaplength = n 

     if i in taken: 
      if gaplength > longestgaplength: 
       longestgaplength = gaplength 
       longestgapstart = gapstart 
      gaplength = 0 
     else: 
      if i == n: 
       if gaplength > longestgaplength: 
        longestgaplength = gaplength 
        longestgapstart = gapstart 
      else: 
       if gaplength == 0: 
        gapstart = i 
       gaplength += 1 

    if longestgapstart == 1: 
     return 1 
    elif longestgapstart + longestgaplength == n and n not in taken: 
     return n 
    else: 
     return longestgapstart + (longestgaplength-1)/2 

print findnextseat(10,[1,10]) #5 
print findnextseat(10,[5,10]) #1 
print findnextseat(10,[1,5,10]) #7 
print findnextseat(10,[1,3])  #10 
print findnextseat(10,[1,2,4,5,6,7,8,9]) #3 

Заслуга dubov94 для алгоритма и Jasper для указания правильного решения для тестового примера.