Pythonで全員が席に着くことができるかどうかをチェックするプログラム

番号nがあり、座席を検索している人がn人いるとすると、ビットのリストもあります。ここで、1はすでに占有されている座席を表し、0は空いている座席を表します。 2人が隣同士に座ることはできないので、n人全員が席を見つけることができるかどうかを確認する必要があります。

したがって、入力がn =2シート=[1、0、0、0、1、0、0]の場合、インデックス2と6にシートできるため、出力はTrueになります。

これを解決するには、次の手順に従います-

• 座席の先頭に0を挿入し、座席の末尾に[0、1]を挿入します
• res：=0、gap：=0
• 座席のiごとに、
  • iが0と同じ場合、
    • ギャップ：=ギャップ+1
  • それ以外の場合、ギャップ> 0の場合、
    • res：=res +（gap-1）/2のフロア
    • ギャップ：=0
• res> =nの場合はtrueを返し、それ以外の場合はfalseを返します

例

理解を深めるために、次の実装を見てみましょう-

def solve(n, seats):
   seats = [0] + seats + [0, 1]
   res = 0
   gap = 0
   for i in seats:
      if i == 0:
         gap += 1
      elif gap > 0:
         res += (gap - 1) // 2
         gap = 0
   return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))

入力

2, [1, 0, 0, 0, 1, 0, 0]

出力

True