根据社交距离准则将用餐者定位在 table 的算法

Question

正在尝试解决此任务：

一家自助餐厅table由一排N个座位组成，从左到右编号为1到N。保持社交距离的准则要求每位就餐者的座位都保持空着，左侧 K 个座位和右侧 K 个座位（如果少于 K 个，则该侧的所有剩余座位）保持空着。 table目前有M位就餐者，第i位坐在S(i)位。

没有两个用餐者坐在同一个座位上，并且满足社交距离准则。假设现有用餐者不能移动，并且额外的用餐者将合作以最大限度地增加任何新的或现有的用餐者，确定在不违反任何新的或现有的用餐者的社交距离准则的情况下可以坐在 table 的额外用餐者的最大数量他们可以坐下来。请注意编写一个在时限内运行的解决方案。

Constraints:

1 <= N <= 10^{15} 
1 <= K <=  N
1 <= M <= 500000
M <= N
1 <= S(i) <= N

Sample test case #1
N = 10
K = 1
M = 2
S = [2, 6]
Expected Return Value = 3

Sample test case #2
N = 15
K = 2
M = 3
S = [11, 6, 14]
Expected Return Value = 1

示例说明

第一种情况，自助餐厅table有N=10个座位，目前有两个食客，分别在2号和6号座位。 table 最初看起来如下，括号覆盖了每个现有餐厅左侧和右侧的 K=1 个座位，可能不会被占用。

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

在不违反社交距离准则的情况下，另外三位用餐者可以坐在 4、8 和 10 号座位。在第二种情况下，只有 1 位额外的用餐者可以坐在前 3 个座位中的任何一个，从而加入 table。

我的解决方案适用于两个测试用例（1 和 2）：

def getMaxAdditionalDinersCount(N: int, K: int, M: int, S: List[int]) -> int:
        
    if N == 0:
        return 0
    
    if K == 0:
        return N
    
    if not S or M == 0:
        return N // (K+1)
    
    pos_cnts = 0   # updated position counts    
    l = sorted(S)  # sort positions in increasing order
   
    first_used_pos = l[0]
    last_used_pos = l[len(l)-1]
    max_pos = N
    tail_len = max_pos - last_used_pos

    # if zero position is not taken yet
    if (1 not in S):
        new_pos_cnt  = first_used_pos // (K+1) - 1
        pos_cnts += new_pos_cnt # update count of all positions
     
    # if last position is not taken yet
    if max_pos not in S:
        new_pos_cnt  = tail_len // (K+1)
        pos_cnts += new_pos_cnt # update count of all positions
    
    indx_prev = l[0]  # index of previous position 
    for indx in l[1:]: # iterate existing positions
        gap = indx - indx_prev
        new_pos_cnt = gap // (K+1) - 1
        pos_cnts += new_pos_cnt # update count of all positions
        indx_prev = indx        
            
    return pos_cnts

还有一个测试用例：

N = 10
K = 1
M = 2
S = [3,5]

它 returns 错误的答案是 2 而不是 3，没有考虑空闲位置 1。正确的算法是什么？

Answer 1

问题出在检查第一个位置的 if 条件中：

# if zero position is not taken yet
if (1 not in S):
    new_pos_cnt  = first_used_pos // (K+1) - 1
    pos_cnts += new_pos_cnt # update count of all positions

问题是当除法有余数的时候你要区别对待。您需要修改 new_pos_cnt 计算，以便在有余数时不减去位置：

# if zero position is not taken yet
if (1 not in S):
    if first_used_pos // (K+1) == first_used_pos / (K+1):
       new_pos_cnt  = first_used_pos // (K+1) - 1
    else:
       new_pos_cnt  = first_used_pos // (K+1) 
    pos_cnts += new_pos_cnt # update count of all positions

前两个测试用例的结果相同，第三个用例的结果也是正确的。

For the testcase 1:
first_used_pos = 2
K = 1
first_used_pos // (K+1) -->  2 // (1+1) = 1
first_used_pos /  (K+1) -->  2 /  (1+1) = 1

For the testcase 2:
first_used_pos = 6
K = 2
first_used_pos // (K+1) -->  6 // (2+1) = 2
first_used_pos /  (K+1) -->  6 /  (2+1) = 2

For the testcase 3:
first_used_pos = 3
K = 1
first_used_pos // (K+1) -->  3 // (1+1) = 1
first_used_pos /  (K+1) -->  3 /  (1+1) = 1.5 # Remainder exist -> don't subtract

根据社交距离准则将用餐者定位在 table 的算法

Algorithm to position diners at a table with social distancing guidelines

python

algorithm