Количество возможных рассадок в кинозале для соблюдения социальной дистанции

Опубликовано: 19 Сентября, 2022

In the COVID times, a movie theatre has to follow a Social distance rule where every two seated individuals must have at least 6 feet distance between them. 

Дан список из N неотрицательных целых чисел, где list[k] — расстояние между k-м местом и (k + 1)-м местом , а в одном ряду — (N+1) мест. Узнайте количество действительных рассадок. Также действительна договоренность без сидячих мест.

Примеры:

Input: list = {5, 2, 4, 1, 2} 
Output: 16
Explanation: As per the given list the seats are arranged as:
S1 <–5–> S2 <–2–> S3 <–4–> S4 <–1–> S5 <–2–> S6
This has 16 possible seating arrangements
These are the valid combinations (1 means taken):
000000 101000 000010 100001
100000 000100 100010 010001
010000 100100 010010 001001
001000 010100 000001 101001

Input: list =  {8, 10, 16}
Output: 16
Explanation: This has 16 possible seating arrangements
Every combination is a valid combination. Four seats => 2^4 combinations.

Наивный подход: Наивный подход заключается в использовании поиска с возвратом. На каждом заданном месте есть два варианта: сидеть или не сидеть. Посетите все возможные договоренности и найдите правильные решения. Выполните шаги, указанные ниже:

  • Начните с первого места.
  • Для каждого места проверьте, действительно ли расстояние от предыдущего места.
  • Если не подходит, переходите на следующее место.
  • Если верно, то есть две возможности: либо сидеть, либо не сидеть. Используйте оба варианта и переходите к следующему месту.
  • Используйте эти критерии рекурсивно для всех мест.
  • Общее количество аранжировок, найденных в конце, является искомым ответом.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(2 N )
Вспомогательное пространство: O(N)

Эффективный подход. Эффективным подходом является использование динамического программирования. Используйте массив dp[] для хранения возможных рассадок до i -го места. Проверьте каждое место, начиная с 1-го. Если расстояние между текущим местом 'i' и предыдущим местом 'j' допустимо (>= 6), добавьте dp[j] к dp[i] . В основном это означает, что и предыдущее место, и текущее место могут быть заняты вместе. Общее количество способов сесть увеличится на количество способов сесть на предыдущее место. Выполните шаги, указанные ниже:

  • Начните итерацию с первого места.
  • Для каждого места проверьте, является ли расстояние от ранее занятого места действительным или нет.
  • Если верно, то увеличьте количество возможных расстановок на расстановки ранее занятого места.
  • Если нет, оставьте договоренности без изменений и перейдите к следующему месту.
  • Окончательное значение на последнем месте является требуемым ответом.

Ниже приведена реализация описанного выше подхода.


Временная сложность: O(N 2 )
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ