Расположите игроков в футбольной команде в соответствии с их высотой

Question

Мне недавно задали этот вопрос в интервью. Вопрос в следующем:

Приведены высоты игрока двух футбольных команд в массиве A и массиве B соответственно. Теперь вы должны указать, можете ли вы организовать команду для фотографирования со следующим ограничением.

1. Одна команда будет стоять в одном ряду (все игроки одной команды должны быть вместе).
2. Рост игрока одной команды, стоящей впереди, должен быть меньше, чем рост игрока другой команды, стоящей за ним.

Ответьте на следующий вопрос: что, если есть N команд, что будет быть максимальным числом команды K, которое вы можете выбрать для фотографии таким образом, чтобы они соответствовали вышеуказанным ограничениям.

Я нашел решение для 2 групп, но не мог придумать решение для последующего вопроса.

Answer 1

Учитывая две команды, мы можем сказать, могут ли обе быть на картине вместе, и если да, то какая из них впереди. Как говорит @typewriter, это приводит к частичному порядку. Этот частичный порядок может быть представлен в виде ациклического c ориентированного графа.

На данный момент мы можем применить любой известный алгоритм Топологическая сортировка для получения линейного порядка.

И теперь мы обрабатываем команды в таком порядке и храним следующие две части информации для каждой команды:

1. Сколько команд может быть перед этим на картинке ?

2. Какова следующая команда перед ними на этом максимальном изображении?

(Мы определяем это, выбирая предыдущую команду, которая может быть в той же картине с максимально возможной картиной. Мы помечаем это как следующую команду, и эта команда может иметь еще одну команду в картине. Это пример динамического алгоритма программирования c.

Когда мы закончим обработку всего списка, ищите команду, в которой может быть больше команд. А затем просмотрите структуру данных, чтобы выяснить, какие команды должны быть на рисунке.

Если есть N команд из M игроков, этот алгоритм должен работать в O((N + log(M)) * N * M). Бит O(log(M) * N * M) относится к N видам отдельных команд. Бит O(N^2 * M) - это поиск всех парных сравнений команд. Топологическая сортировка и динамический бит программирования c быстры относительно второго шага.

Answer 2

Это интересный вопрос. Для двух команд вы можете отсортировать обе команды по длине. Если $ n $ -ый член в команде A длиннее, чем $ n $ -ый член в команде B, то команды сравнимы в смысле POSET. Т.е. вы можете сказать, что команда A длиннее, чем команда B.

Не каждая команда сопоставима таким образом. Сортированные команды увеличиваются в высоте, но увеличивающиеся функции могут все еще пересекаться. Поскольку не каждая пара команд сопоставима, совокупность всех команд называется частично упорядоченным набором или POSET. Вы можете взглянуть на это: https://people.math.gatech.edu/~trotter/math-3012/3012-Lecture-14.pdf.

Следующая часть вопроса может быть интерпретирована как определение высоты этого ПОЗЕТА. то есть какое наибольшее количество команд может уместиться на одной фотографии.

Я не смог найти явный алгоритм поиска в Google, но я уверен, что он существует.